学步园

抓狂 = =。。

最水最短路，好久没做了，做一道试试 = =。结果让我检查了好久 = =。

开始忘了让它弄成双向的那句话= =。

然后一直RE = =。发现 t和n输入反了 = =。。。我去死吧 = =

#include <iostream><br /> #include <stdlib.h><br /> #include <limits.h><br /> #include <string.h><br /> using namespace std;<br /> int map[1010][1010];<br /> int dis[1010];<br /> int n,pos,sum;<br /> void init()<br /> {<br /> for(int i=0; i<1001; i++)<br /> {<br /> for(int k=0; k<1001; k++)<br /> map[i][k] = INT_MAX;<br /> map[i][i] = 0;<br /> }<br /> for(int i=0; i<1001; i++)<br /> dis[i] = INT_MAX;<br /> sum = 0;<br /> }<br /> void Dijkstra()<br /> {<br /> int used[1010];<br /> memset(used,0,sizeof(used));<br /> int now = pos;<br /> dis[now] = 0; used[now] = 1;<br /> for(int i=0; i<n; i++)<br /> {<br /> for(int k=1; k<=n; k++)<br /> if( map[now][k] != INT_MAX && dis[now] + map[now][k] < dis[k] )<br /> dis[k] = dis[now] + map[now][k];<br /> int min = INT_MAX;<br /> for(int k=1; k<=n; k++)<br /> if( dis[k] < min && !used[k] )<br /> min = dis[now = k];<br /> used[now] = 1;<br /> }<br /> }<br /> int main()<br /> {<br /> int from,to,len,t;<br /> init();<br /> cin >> t >> n;<br /> pos = n;<br /> for(int i=1; i<=t; i++)<br /> {<br /> cin >> from >> to >> len;<br /> if( len < map[from][to] )<br /> map[from][to] = map[to][from] = len;<br /> }<br /> Dijkstra();<br /> cout << dis[1] << endl;<br /> return 0;<br /> }<br />