题解 P1807 【最长路_NOI导刊2010提高（07）】

· · 题解

哇

竟然没有人写dijkstra？？？

给了我这个不写spfa的蒟蒻一个机会啊2333

以上都是废话

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

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

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

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

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

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

奉上代码

#include<bits/stdc++.h> // 万能头文件

using namespace std;

int dis[10001];
bool used[10001]; // 意义就跟平常的dijkstra一样
// 存图采用邻接表
vector < int > g[10001]; // 表示第i个点的第j条边的目的地是g[i][j] 
vector < int > gv[10001]; // 表示第i个点的第j条边的权值是gv[i][j] 
int lv[10001]; // 表示第i个点有lv[i]条边 

int main(){
    int n, m, s = 1; // s为起点
    memset(dis, -1, sizeof(dis)); // 初始化
    memset(used, 0, sizeof(used));
    memset(lv, 0, sizeof(lv));
    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);
    }
    //-------------读入完毕----------------
    dij[s] = 0;
    for(int t = 1; t <= n; t++){
        int Min = -1, u; // （这边叫Min只是因为抄了我单源最短路的代码，没有实际意义）
        for(int i = 1; i <= n; i++){ // 找到没有被锁定的编号最小的点
            if(!used[i] && dij[i] != -1){
                Min = dij[i];
                u = i;
                break;
            }
        }
        used[u] = 1; // 锁定该点
        for(int i = 1; i <= lv[u]; i++){ // 向外拓展
            if((dij[g[u][i]] == -1 || Min + gv[u][i] > dij[g[u][i]]) && !used[g[u][i]])
                dij[g[u][i]] = gv[u][i] + Min;
        }
    }
    printf("%d", dij[n]);
    // 直接输出（因为我用-1表示无法到达）
}