Til the Cows Come Home POJ

题目链接：https://cn.vjudge.net/problem/POJ-2387#author=dusenlin

注意：输入的时候，两点之间可能有多条边，选则边权最小的

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 #include <stack>
 6 #include <algorithm>
 7 #include <cmath>
 8 #include <map>
 9 #define mem(a,b) memset(a,b,sizeof(a));
10 using namespace std;
11 #define INF 0x3f3f3f3f
12 typedef long long ll;
13 int dir[4][2] = {0,1,0,-1,1,0,-1,0};
14 const int maxn = 5000005;
15 int t,n,edge[1005][1005],d[1005],vis[1005];
16 void Dijkstra(int s) {
17     mem(vis,0);
18     mem(d,INF);
19     d[1] = 0;
20     for(int i = 1; i <= n; i++) {
21         int maxn = INF,x;
22         for(int j = 1; j <= n; j++) {
23             if(d[j] < maxn&&!vis[j]) {
24                 maxn = d[j];
25                 x = j;
26             }
27         }
28         vis[x] = 1;
29         for(int j = 1; j <= n; j++) {
30             d[j] = min(d[j],d[x]+edge[x][j]);
31         }
32     }
33 }
34 int main(){
35     cin >> t >>n;
36     int a,b,c;
37     mem(edge,INF);
38     for(int i = 0; i < t; i++) {
39         cin >> a >> b >> c;
40         if(c < edge[a][b]){
41         edge[a][b] = c;
42         edge[b][a] = c;
43         }
44     }
45     Dijkstra(1);
46     cout << d[n] << endl;
47     return 0;
48 }