OI题库

【题目描述】

设G为有n个顶点的有向无环图，G中各顶点的编号为1到n，且当为G中的一条边时有i < j。设w（i，j）为边的长度，请设计算法，计算图G中<1，n>间的最长路径。

【输入格式】

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

【输出格式】

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

【样例输入】

2 1
1 2 1

【样例输出】

1

说明：若输入样例为2 0，则输出为-1。

【提示】

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

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

100%的数据，n≤1,500　，m≤50000，最长路径不大于10^9

【来源】

冲刺NOIP2010模拟试题与解析（七）（提高组复赛）