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

· · 题解

终于一遍过了，时隔n月第一次！

几乎裸的spfa，微处理一下

建负边，照着spfa跑（当然memset那里还要正的0x7f，为什么呢？若是负的，想想，肯定wa），那么你的最短路跑出来的结果是负值最小的，再乘-1，不就是正边最大的吗？

废话不多说上代码，一看就会（为什么我要多贴代码？每个人风格都不同，可能你看别人的不太懂看我的会容易理解）

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 50010
using namespace std;
struct EDGE
{
    int next;
    int to;
    int co;
}edge[maxn*5];
int qr,head[maxn],team[maxn],dis[maxn],exist[maxn];
int n,m,flag;
void add(int from,int to,int co)
{
    edge[++qr].next=head[from];
    edge[qr].to=to;
    edge[qr].co=co;
    head[from]=qr;
}
void spfa()
{
    memset(dis,0x7f,sizeof(dis));
    memset(exist,0,sizeof(exist));
    int h=0,t=1;
    dis[1]=0;exist[1]=1;team[1]=1;
    while(h<t)
    {
        h++;
        int u=team[h];
        exist[u]=0;
        for(int i=head[u];i!=0;i=edge[i].next)
         {
             int v=edge[i].to;
             if(dis[v]>dis[u]+edge[i].co)
              {
                  dis[v]=dis[u]+edge[i].co;
                  if(!exist[v])
                   {
                       exist[v]=1;
                       t++;
                       team[t]=v;
                   }
                if(v==n)
                 flag=1;
              }
         }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
     {
         int a,b,v;
         cin>>a>>b>>v;
         add(a,b,-v);
     }
    spfa();
    if(!flag) printf("-1");
     else printf("%d",-dis[n]);
    return 0;
}