题目名称	1124. [NOIP 2010冲刺七]最长路
输入输出	`longest.in/out`
难度等级	★☆
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	9
题目来源	sywgz 于2012-10-08加入
开放分组	全部用户
提交状态
分类标签	最短路图论
	分享题解

通过：164，提交：392，通过率：41.84%
Qw	100	0.018 s	0.90 MiB	C++
ShallowDream雨梨	100	0.018 s	4.91 MiB	C++
KZNS	100	0.019 s	0.33 MiB	C++
zxj	100	0.019 s	2.36 MiB	C++
明天	100	0.020 s	0.75 MiB	Pascal
明天	100	0.021 s	0.75 MiB	Pascal
面对疾风吧疾风疾风吧	100	0.022 s	0.12 MiB	C++
小薛也嘻哈	100	0.022 s	0.34 MiB	C++
Marvolo	100	0.022 s	0.37 MiB	C++
甘罗	100	0.022 s	0.37 MiB	C++

本题关联比赛
20121009
防止浮躁的小练习V0.1

关于最长路的近10条评论(全部评论)
按最短路写都能过四个点。。。。淼淼淼淼淼淼淼淼淼淼 HeHe 2017-07-04 10:48 8楼
Hzoi_Go灬Fire 2016-10-07 17:30 7楼
Dijs比SPFA慢！手写双端队列比STL慢！SPFA的SLF优化比不优化慢！…… NewBee 2016-08-28 14:49 6楼
1A SOBER GOOD BOY 2016-08-28 12:08 5楼
这不科学，我的Bellman-Ford居然W了好吧= =数组开小了 AntiLeaf 2016-08-28 11:17 4楼
一开始把所有边权都取了相反数求最短路，后来发现直接把spfa中松弛操作的‘<'改成'>'也可以。。。 liu_runda 2016-01-25 15:22 3楼
回复 @cstdio : LPFA、、、乌龙猹 2014-10-24 16:48 2楼
SPFA…… cstdio 2012-12-05 21:27 1楼

1124. [NOIP 2010冲刺七]最长路

★☆ 输入文件：longest.in 输出文件：longest.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

设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

【样例输出】

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

【提示】

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

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

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

【来源】

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