a833: 3、沙漠旅行
Tags : 图论
Accepted rate : 58人/61人 ( 95% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-11-29 02:07

Content
    小X和小Y某天头脑发热,携手来到了一片沙漠,作为自己的假期旅行。然而,天有不测风云,突然刮起沙尘暴,两人不幸走散了。小X为了找到小Y,决定拿出自己新研发的定位和传送系统。由于该系统还不成熟,只能找到地图上有限的n个关键点,并支持m对关键点之间的单向传送。传送理论上只需要耗费1的时间,但同样由于该系统还不成熟,有些传送需要耗费2的时间才能保证传送的安全。尽管系统不成熟,对于小X自己以及小Y所在的位置自然是格外敏感的。因此,小X所在的位置是关键点1,小Y所在的位置是关键点n,且小X一定能找到小Y。现在,小X想用最短的时间找到小Y,希望你能帮他算出这个时间。
Input
    输入的第一行包含两个整数n和m。接下来m行,每行包含三个整数ui,vi,wi(ui≠vi),表示可以用wi的时间从ui单向传送到vi
Output
输出一行包含一个整数,表示小X找到小Y的最短时间。
Sample Input #1
4 5
1 3 1
2 4 2
1 2 2
3 4 2
2 4 1
Sample Output #1
3
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.0s , <1K
公開 測資點#1 (5%): 1.0s , <1M
公開 測資點#2 (5%): 1.0s , <1M
公開 測資點#3 (5%): 1.0s , <1M
公開 測資點#4 (5%): 1.0s , <1M
公開 測資點#5 (5%): 1.0s , <1M
公開 測資點#6 (5%): 1.0s , <10M
公開 測資點#7 (5%): 1.0s , <10M
公開 測資點#8 (5%): 1.0s , <10M
公開 測資點#9 (5%): 1.0s , <10M
公開 測資點#10 (5%): 1.0s , <1K
公開 測資點#11 (5%): 1.0s , <1M
公開 測資點#12 (5%): 1.0s , <1M
公開 測資點#13 (5%): 1.0s , <1M
公開 測資點#14 (5%): 1.0s , <1M
公開 測資點#15 (5%): 1.0s , <1M
公開 測資點#16 (5%): 1.0s , <10M
公開 測資點#17 (5%): 1.0s , <10M
公開 測資點#18 (5%): 1.0s , <10M
公開 測資點#19 (5%): 1.0s , <10M
Hint :

1≤n,m≤5×105

备战Noip 2013模拟赛系列第三题 

Tags:
图论
出處:
备战Noip 2013模拟赛系列 [管理者:
abs2000 (重回zerojudge立志刷榜...)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」