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

· · 题解

用普通的SPFA就能过，就是要注意队列要开的大一些，不然会WA几个点，我自己因为队列开的小调了好久，程序在下方

代码中用数组模拟邻接表存边，存边时代码很精简，可以学习一下，我也是跟别人学的。

#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN=1505,MAXM=50005;
int firstEdge[MAXN],endPoint[MAXM],nextEdge[MAXM],p;
int myQueue[500005],tail=0,head=0,n,m,t;
int weight[MAXM],dist[MAXN];
int main()
{
    cin>>n>>m;
    for(int i=2;i<=n;i++)dist[i]=-1;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&t,&endPoint[i],&weight[i]);
        nextEdge[i]=firstEdge[t]; firstEdge[t]=i;
    };
    myQueue[tail++]=1;
    while(tail>head)
    {
        t=myQueue[head++];
        p=firstEdge[t];
        while(p)
        {
            if(dist[endPoint[p]]<dist[t]+weight[p])
            {
                dist[endPoint[p]]=dist[t]+weight[p];
                myQueue[tail++]=endPoint[p];
            };
            p=nextEdge[p];
        };
    };
    cout<<dist[n];
    return 0;
}