P1807 最长路

其实这跟普通的dijkstra没有太大区别

核心思路就是根据题面里面的这句“当为G中的一条边时有i < j”

所以当前没有被锁定的编号最小的点不会被更新（这句话比较关键）

由此我们可以将dijkstra原本由“没有被锁定的dis最小的点”向外拓展改为由“没有被锁定的编号最小的点”向外拓展

接下来，我们需要改一下松弛:

• 直接根据体面，将原来的路径长度越小越好改为越大越好，就行了

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int f[N], lv[N], n, m, s = 1;
bool u[N];
vector <int> g[N], gv[N];
int main(){
    memset(f, -1, sizeof f);
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        lv[a]++;
        if(lv[a] == 1) g[a].push_back(-1), gv[a].push_back(-1);
        g[a].push_back(b), gv[a].push_back(c);
    }
    f[s] = 0;
    for(int t = 1; t <= n; t++){
        int Min = -1, U;
        for(int i = 1; i <= n; i++)
            if(!u[i] && f[i] != -1){
                Min = f[i];
                U = i;
                break;
            }
        u[U] = 1;
        for(int i = 1; i <= lv[U]; i ++ )
            if((f[g[U][i]] == -1 || Min + gv[U][i] > f[g[U][i]]) && !u[g[U][i]])
            	f[g[U][i]] = gv[U][i] + Min;
    }
    printf("%d", f[n]);
}