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

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
using namespace std;
int n,m,answer=-1;
vector<int>a[1510];
vector<int>b[1510];
void bfs(int x);
int main()
{
    freopen ("longest.in","r",stdin);
    freopen ("longest.out","w",stdout);
    cin>>n>>m;
    for (int i=0;i<m;i++)
    {
        int r,t,v;
        cin>>r>>t>>v;
        a[r].push_back(t);
        b[r].push_back(v);
    }
    bfs(1);
    cout<<answer;
    return 0;
}

void bfs(int x)
{
    int w[1510]={0};
    bool used[1510]={0};
    int q[60000]={0};
    int tou,wei;
    tou=wei=0;
    q[0]=x;
    used[x]=1;
    for (int i=0;i<=n;i++)
        w[i]=-1;
    w[x]=0;
    while (tou<=wei)
    {
        for (int i=0;i<a[q[tou]].size();i++)
        {
            int j;
            j=a[q[tou]][i];
            if (!used[j]&&w[q[tou]]+b[q[tou]][i]>w[j])
            {
                wei++;
                q[wei]=j;
                w[j]=w[q[tou]]+b[q[tou]][i];
                used[j]=1;
            }
            if (used[j]&&w[q[tou]]+b[q[tou]][i]>w[j])
            {
                w[j]=w[q[tou]]+b[q[tou]][i];
            }
        }
        used[q[tou]]=0;
        tou++;
    }
    answer=w[n];
}