记录编号	43410	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	TBK	是否通过	通过
代码语言	C++	运行时间	0.067 s
提交时间	2012-10-10 13:37:00	内存使用	41.34 MiB

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> v[1501],w[1501];
int a,b,c,d,l,m,n,s,p[10000000],r[1501],h=1,t;
bool bo[1501];
void SPFA(void)
{
    p[0]=1;
    r[1]=0;
    while (h>t)
    {
        bo[p[t]]=false;
        for (d=0;d<v[p[t]].size();d++)
            if (r[p[t]]+w[p[t]][d]>r[v[p[t]][d]])
            {
                r[v[p[t]][d]]=r[p[t]]+w[p[t]][d];
                if (bo[v[p[t]][d]]==false) 
                {
                    bo[v[p[t]][d]]=true;
                    p[h]=v[p[t]][d];
                    h++;
                }
            }
        t++;
    }
}
int main(void)
{
    freopen ("longest.in","r",stdin);
    freopen ("longest.out","w",stdout);
    scanf("%d%d",&a,&b);
    if (b==0)
    {
        printf("-1");
        return 0;
    }
    for (c=0;c<b;c++)
    {
        scanf("%d%d%d",&l,&m,&n);
        v[l].push_back(m);
        w[l].push_back(n);
    }
    SPFA();
    s=r[a];
    if (s==0) s=-1;
    printf("%d",s);
    fclose(stdin);
    fclose(stdout);
    return 0;
}