回『原創/不分類題庫』
d243. 圖論專家
標籤 :
通過比率 : 40人/44人 ( 91% ) [非即時]
評分方式：
Tolerant

最近更新 : 2009-04-25 17:40

內容

shik 跟 nanj 爭論

誰的圖論強

於是比了一題ACM的最短路徑

 沒想到shik秒殺了它

nanj 說   可惡!!!!我輸了

於是對shik下了挑戰

出了一個題目

找出第K短路徑

shik遇到的難題

各位程式好手，幫幫shik解決難題吧 

 

 //結果shik  第一個AC了  

 // shik太威了 

 

輸入說明

多組測試資料

第一行 0<n, m<100  n是個數(編號從0~n-1) m是邊數

接下來的m行

有三個數字  x y d

代表 x 到 y 距離 d (雙向邊)

接下來有 p 組詢問

在下來的p行 

有三個數字 s t k (k<50)

從s到t的第k短 

 

 

輸出說明

找出第K短的路徑長

找不到輸出"?"

見範例測資

1~k短的路徑長要每條都不一樣長

 

範例輸入 #1 
5 5
0 1 10
1 2 5
1 4 2
2 3 1
0 2 4
4
0 1 2
0 2 10
0 3 11
0 4 5
5 5
0 1 10
1 2 5
1 4 2
2 3 1
0 2 4
1
5 6 5
範例輸出 #1 
Set #1
10
18
20
16
Set #2
?
測資資訊：
記憶體限制： 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
提示 ：
標籤:
出處:
[管理者： nanj0178 (nanj) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」