內容
湯姆住在一個大的城市，他星期一至五每天坐公共汽車到他的辦公室上班。若全市有n個車站，編號為0，1，.............，n - 1。已知湯姆的家是在車站0，他的辦公室是在車站編號n-1，而公共汽車路徑已被設計為一個有向圖，該頂點表示公共汽車站，而連接線的線條樣式，代表至該車站的費用。你的任務是寫一個程式來幫助湯姆計算從他的家(車站0)到他的辦公室(車站n-1)的最低車票費用。
下圖顯示了一個例子。還有在這個城市的9個車站。若連接車站的線條是一條實線、虛線、雙實線，則車票費用分別為6、1、3，則此例的最低車票費用為87。
輸入說明
第一行只有一個整數n，代表車站數量，接下來會有n行，每行有n個整數，以空白分開。而第i (i<=n-1)行第j (j<=n-1)個數字，代表第i個車站到第j個車站的車票費用，若費用為-1，代表沒有公車可以從第i站直達到第j站。
輸出說明
輸出從湯姆家(車站編號0)到辦公室(車站編號n-1)，搭公車所花的最少車票費用。
範例輸入
#1
9 -1 3 -1 3 6 -1 -1 -1 -1 -1 -1 1 -1 3 6 -1 -1 -1 -1 -1 -1 -1 1 3 -1 -1 -1 -1 -1 -1 -1 3 -1 1 6 -1 -1 -1 -1 -1 -1 1 -1 1 6 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 -1 5 3 -1 -1 -1 -1 -1 4 9 -1 2 -1 -1 -1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1
範例輸出
#1
7 14
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1M
公開 測資點#0 (50%): 1.0s , <1K
公開 測資點#1 (50%): 1.0s , <1M
提示 ：
Dijkstra演算法
標籤:
出處:
2010 ISSC 第8次模擬賽第3題
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||