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

· · 题解

emmmm……

楼下怎么都是SPFA呢orz

那本人水一发Bellman-Ford吧……

思路楼下讲的很清楚：

  1. 把最长边转换为最短边（也就是取负值啦）

  2. 跑一遍最短路模板(点点有惊喜)

  3. 最后的答案在取负回来

注意到达不了的情况（可以跑一遍遍历，但本人很懒就随便过了……）

下面放上丑陋美丽的ACcode：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int dis[50001],w[50001],n,m,minn,f[50001][3];
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        dis[i]=w[i]=100000000;
        f[i][1]=f[i][2]=0;
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        f[i][1]=a,f[i][2]=b,w[i]=-c;
    }
    dis[1]=0;
    for(int i=1;i<=n-1;i++){
        for(int j=1;j<=m;j++){
            dis[f[j][2]]=min(dis[f[j][2]],dis[f[j][1]]+w[j]);
        }
    }
    if(dis[n]!=0)
    printf("%d",-dis[n]);
    else printf("-1");
    return 0;
}

ps:Bellman-Ford算法不用判断重边，最短路该怎么求就怎么求

pps:拒绝抄袭，营造良好洛谷

ppps:如果代码有错误请回复，感激不尽~~~~

pppps:觉得有帮助就点个赞呗~~~~