2407 問題 E: 信息學(xué)奧賽一本通T1498-Roadblocks
時間限制: 1s
內(nèi)存限制: 128MB 提交: 49 解決: 21
題目描述
原題來自：USACO 2006 Nov. Gold
貝茜把家搬到了一個小農(nóng)場，但她常?；氐?FJ 的農(nóng)場去拜訪她的朋友。貝茜很喜歡路邊的風(fēng)景，不想那么快地結(jié)束她的旅途，于是她每次回農(nóng)場，都會選擇第二短的路徑，而不象我們所習(xí)慣的那樣，選擇最短路。
貝茜所在的鄉(xiāng)村有 R(1≤R≤105) 條雙向道路，每條路都連接了所有的 N(1≤N≤5000) 個農(nóng)場中的某兩個。貝茜居住在農(nóng)場 1，她的朋友們居住在農(nóng)場 N（即貝茜每次旅行的目的地）。
貝茜選擇的第二短的路徑中，可以包含任何一條在最短路中出現(xiàn)的道路，并且一條路可以重復(fù)走多次。當(dāng)然第二短路的長度必須嚴(yán)格大于最短路（可能有多條）的長度，但它的長度必須不大于所有除最短路外的路徑的長度。
輸入
第 1 行為兩個整數(shù)，N 和 R，用空格隔開；
第 2…R+1 行：每行包含三個用空格隔開的整數(shù) A、B 和 D，表示存在一條長度為 D(1≤D≤5000) 的路連接農(nóng)場 A 和農(nóng)場 B。
輸出
輸出僅一個整數(shù)，表示從農(nóng)場 1 到農(nóng)場 N 的第二短路的長度。
樣例輸入
4 4
1 2 100
2 4 200
2 3 250
3 4 100
提示
最短路：1→2→4（長度為 100+200=300）
第二短路：1→2→3→4（長度為 100+250+100=450）