a259.
10917 - A Walk Through the Forest
內容
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。
範例輸入
#1
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
範例輸出
#1
2 4 3 1
測資資訊：
記憶體限制：
512
MB
提示 ：
2011/10/23 02:00 am 修正測資，感謝 david942j 提出錯誤，已手動全部重測。
各位非常抱歉！！！
標籤:
出處:
UVa10917
[管理者：
m80126colin
(許胖)
]