hdu-1874 畅通工程续---模板题

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1000 + 10;
 5 const int INF = 0x3f3f3f3f;
 6 int Map[maxn][maxn];
 7 int v[maxn], d[maxn];
 8 int n, m;
 9 
10 void dijkstra(int s, int t)
11 {
12     memset(v, 0, sizeof(v));
13     for(int i = 0; i <= n; i++)d[i] = (i == s ? 0 : INF);
14     for(int i = 0; i < n; i++)
15     {
16         int x = -1, m = INF;
17         for(int i = 0; i < n; i++)if(!v[i] && d[i] <= m)m = d[x = i];
18         v[x] = 1;
19         for(int i = 0; i < n; i++)
20         {
21             if(d[i] > d[x] + Map[x][i])
22             {
23                 d[i] = d[x] + Map[x][i];
24             }
25         }
26     }
27     if(d[t] == INF)d[t] = -1;
28     cout<<d[t]<<endl;
29 }
30 
31 int main()
32 {
33     while(scanf("%d%d", &n, &m) != EOF)
34     {
35         int u, v, w, s, t;
36         memset(Map, INF, sizeof(Map));
37         while(m--)
38         {
39             scanf("%d%d%d", &u, &v, &w);
40             Map[u][v] = Map[v][u] = min(w, Map[u][v]);
41         }
42         scanf("%d%d", &s, &t);
43         dijkstra(s, t);
44     }
45 }