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

doby · 2017-08-06 23:58:22 · 题解

既然Bellman-ford能过……

SPFA咋就没个代码呢……

反着搞最短路初始化和松弛就可以了……

另外肯定是单向边，不然就是类似最短路里的负权环一样，直接正无限上去了……

#include<cstdio>
#include<queue>
using namespace std;
int n,m,s,x,y,z,out,fh,cnt,top,head[1510],dis[1510];
bool done[1510];
char cc;
deque<int>q;
struct Edge
{
    int to,next,dis;
}e[100010];
int read()//能读负数但是会变慢的读入优化
{
    out=0,fh=1,cc=getchar();
    while((cc<'0'||cc>'9')&&cc!='-'){cc=getchar();}
    if(cc=='-'){fh=-1,cc=getchar();}
    else{out=cc-'0',cc=getchar();}
    while(cc>='0'&&cc<='9')
    {
        out=out*10+cc-'0',
        cc=getchar();
    }
    return out*fh;
}
void add(int x,int y,int z)//增加单向边的操作
{
    cnt++,e[cnt].next=head[x],e[cnt].to=y,e[cnt].dis=z,head[x]=cnt;
}
void SPFA(int s)
{
    for(int i=1;i<=n;i++){dis[i]=-233333333;}
    dis[s]=0,done[s]=1;
    q.push_back(s);
    while(!q.empty())
    {
        x=q.front();
        q.pop_front();
        for(int i=head[x];i;i=e[i].next)
        {
            y=e[i].to;
            if(dis[y]<dis[x]+e[i].dis)
            {
                dis[y]=dis[x]+e[i].dis;
                if(!done[y])
                {
                    done[y]=1;
                    if(!q.empty())
                    {
                        if(dis[y]<dis[q.front()]){q.push_back(y);}
                        else{q.push_front(y);}
                    }
                    else{q.push_back(y);}
                }
            }
        }
        done[x]=0;
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        add(x,y,z);
    }
    SPFA(1);
    printf("%d",(dis[n]==-233333333?-1:dis[n]));//最后用三目判断一下是否还是初始值就好了……
    return 0;
}