记录编号	43567	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	cqb	是否通过	通过
代码语言	C++	运行时间	0.047 s
提交时间	2012-10-11 18:36:12	内存使用	3.50 MiB

#include <cstdio>
using namespace std;
int n,m,i,x,y,len,l,li[100005],num[100005],next[100005],dis[1505],head[1505],q[100000];
bool b[1505];
void SPFA(){
     int f=1,r=1,x;q[1]=1;
     while (f<=r){
           x=q[f];b[x]=0;
           for (i=head[x];i;i=next[i]){
               if (dis[x]+li[i]>dis[num[i]]){
                  dis[num[i]]=dis[x]+li[i];
                  if (!b[num[i]]){
                     b[num[i]]=1;
                     q[++r]=num[i];
                  }
               }
           }
           f++;
     }
}
int main(){
    freopen("longest.in","r",stdin);
    freopen("longest.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&len);
        l++;li[l]=len;num[l]=y;next[l]=head[x];head[x]=l;
    }
    SPFA();
    if (dis[n]==0) printf("-1\n");else
    printf("%d\n",dis[n]);
    return 0;
}