记录编号	43478	评测结果	AAAAAAAAA
题目名称	[NOIP 2010冲刺七]最长路	最终得分	100
用户昵称	11111111	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2012-10-10 20:01:47	内存使用	32.47 MiB

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
int i,j,k,n,m,l,r,t,x,y;
int ll[1600][1600][3]={0},s[1600]={0},bian[1600];
int b[1600];
bool v[1600]={false};
int main()
{
    ifstream fin("longest.in");
    ofstream fout("longest.out");
    fin>>n>>m;
    for (i=1;i<=m;i++)
	{
        fin>>j>>k>>t;
        bian[j]++;
        ll[j][bian[j]][1]=k;
        ll[j][bian[j]][2]=t;
    }
    l=0;r=1;
    b[1]=1;
    v[1]=true;
    while (l!=r)
	{
        l=(l+1)%n;
        x=b[l];
        v[x]=false;
        for (i=1;i<=bian[x];i++)
		{
            if ((s[ll[x][i][1]]<s[x]+ll[x][i][2])||(s[ll[x][i][1]]==0))
            {
                s[ll[x][i][1]]=s[x]+ll[x][i][2];
                if (!v[ll[x][i][1]]) 
				{
                    v[ll[x][i][1]]=true;
                    r=(r+1)%n;
                    b[r]=ll[x][i][1];
                }
            }
        }
    }
    if (s[n]==0) fout<<"-1";
    else fout<<s[n];
	fin.close();
	fout.close();
    return 0;
}