九度1008,最短路徑問題

<dt>題目1008：最短路徑問題</dt>

<dd></dd>

時間限制：1 秒

記憶體限制：32 兆

特殊判題：否

送出：5119

解決：1631

<dl></dl>

<dt></dt>

題目描述：

給你n個點，m條無向邊，每條邊都有長度d和花費p，給你起點s終點t，要求輸出起點到終點的最短距離及其花費，如果最短距離有多條路線，則輸出花費最少的。

輸入：

輸入n,m，點的編号是1~n,然後是m行，每行4個數 a,b,d,p，表示a和b之間有一條邊，且其長度為d，花費為p。最後一行是兩個數 s,t;起點s，終點t。n和m為0時輸入結束。

(1&lt;n&lt;=1000, 0&lt;m&lt;100000, s != t)

輸出：

輸出 一行有兩個數， 最短距離及其花費。

樣例輸入：

樣例輸出：

來源：

AC

之前用了佛洛依德逾時了，改成C也逾時了，于是用了Dijkstra，Dijkstra和Prim很像，Dijkstra是通過節點k來更新d[j],即:d[j] = d[k] + map[k][j];

而Prim是用剛加入最小生成樹的節點k到j的距離來更新節點j到原最小生成樹的距離，即d[j]=map[k][j]