a259: 10917 - A Walk Through the Forest
標籤 :
通過比率 : 93% (71 人 / 76 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2012-11-14 00:37

內容

Jimmy最近覺得工作壓力很大。為了放鬆心情,他喜歡走路回家。 他的辦公室在森林的一邊,而他的家在森林的另一邊。當他在森林中散步時,看看小鳥、松鼠讓他覺得很快樂。

森林是那麼的美,Jimmy想要每天都走不同的路徑回家。但是他也不想要回家太晚,所以他總是選擇一條可以朝他家「前進」的路徑來走。所謂「前進」指的是他會選擇從A點走到B點如果B點存在一條到他家的路徑長度比A點到他家任一路徑的長度都來的短的話。請你算出Jimmy共有多少種不同的路徑可以走。

輸入說明

輸入包含多組測試資料

每組測試資料的第1列包含2個整數 N ( 1 < N <= 1000)和 M,N代表共有多少個點(編號從1到 N,請注意:編號 1 的點為 Jimmy 的辦公室,編號 2 的點為 Jimmy 的家),M代表共有多少個連接2個點的邊。接下來的M列每列有3個整數 a, b, d。a,b為點的編號,d 為連接 a,b 的路徑長(在這裡 a,b 不會相同,1 <= d <= 1000000)。路徑是雙向的,且任2點之間僅有一條路徑連接。

輸入的最後一列僅有一個 0,請參考Sample Input。

輸出說明
每組測試資料輸出一列,Jimmy共有多少種不同的路徑可以走。你可以假設這個數字不會超過2147483647。
範例輸入
5 6
1 3 2
1 4 2
3 4 3
1 5 12
4 2 34
5 2 24
7 8
1 3 1
1 4 1
3 7 1
7 4 1
7 5 1
6 7 1
5 2 1
6 2 1
5 7
1 3 2
1 4 2
3 4 3
1 5 12
4 2 34
5 2 25
4 5 1000
2 1
1 2 999
0
範例輸出
2
4
3
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <10M
提示 :
2011/10/23 02:00 am 修正測資,感謝 david942j 提出錯誤,已手動全部重測。
各位非常抱歉!!!
標籤:
出處:
UVa10917 [編輯:
m80126colin (許胖)
]


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