Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

设G为有n个顶点的有向无环图，G中各顶点的编号为1到n。设w[i，j]为边的长度。请计算图G中从1到n的最长路径。

【数据范围】

20%的数据，n≤100，m≤1000

40%的数据，n≤1,000，m≤10000

100%的数据，n≤1,500，m≤50000

【输入格式】

　第一行有两个整数n和m,表示有n个顶点和m条边，接下来m行中每行输入3个整数a，b，v表示从a点到b点有一条长度为v的边。

【输出格式】

一个整数，即1到n之间的最长路径。 如果1到n之间没连通，输出-1。

Sample Input

2 1

1 2 1

Sample Output

1

Sample Input2

2 0

Sample Output2

-1

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=t071

【题解】



把spfa的松弛操作换一下改成求最长路就好;

一开始把dis数组赋值为255，这样方便最后的输出;

so easy…TAT只能刷水题的蒟蒻.



【完整代码】

#include <cstdio>

#include <cstring>

#include <vector>

#include <queue>

using namespace std;

const int MAXN = 2000;

int n,m,dis[MAXN];

vector <int> a[MAXN],w[MAXN];

queue <int> dl;

bool inque[MAXN];

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    scanf("%d%d",&n,&m);

    for (int i = 1;i <= m;i++)

    {

        int x,y,z;

        scanf("%d%d%d",&x,&y,&z);

        a[x].push_back(y);

        w[x].push_back(z);

    }

    memset(dis,255,sizeof(dis));

    dis[1] = 0;

    inque[1] = true;

    dl.push(1);

    while (!dl.empty())

    {

        int x= dl.front();

        inque[x] = false;

        dl.pop();

        int len = a[x].size();

        for (int i = 0;i <= len-1;i++)

        {

            int y= a[x][i],c = w[x][i];

            if (dis[y] < dis[x]+c)

            {

                dis[y] = dis[x] +c;

                if (!inque[y])

                {

                    inque[y] = true;

                    dl.push(y);

                }

            }

        }

    }

    printf("%d\n",dis[n]);

    return 0;

}