91分 [求调(马蜂较好)]

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node
{
    int id, size;
}g[1505][1505];

int ans[1505];
int n, m;

void dij()
{
    memset(ans, -1, sizeof(ans));
    priority_queue<int, vector<int>, greater<int> > q;
    q.push(1);
    ans[1] = 0;
    while(!q.empty())
    {
        int x = q.top();
        q.pop();
        for(int i = 1; i <= n; i++)
        {
            if(g[x][i].size < -1e8)
            {
                continue;
            }
            if(ans[i] < ans[x] + g[x][i].size)
            {
                ans[i] = ans[x] + g[x][i].size;
                q.push(i);
            }
        }
    }
}

signed main()
{
    cin >> n >> m;
    memset(g, -0x3f3f3f, sizeof(g));
    for(int i = 1; i <= m; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        if(g[x][y].size < z)
        {
            g[x][y] = node{y, z};
        }
    }
    dij();
    cout << ans[n] << "\n";
}