洛谷 P1339 [USACO09OCT]热浪Heat Wave（最短路）

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 const int inf = 0x3f3f;
 8 int n, c, ts, te, dis[2505], vis[2505], g[5005][5005];
 9 
10 inline void dijkstra(int x){
11     for(int i = 1; i <= n; i++) dis[i] = (i == x ? 0 : inf);
12     for(int i = 1; i <= n; i++){
13         int t = 0, y = inf;
14         for(int j = 1; j <= n; j++) if(!vis[j] && dis[j] <= y) y = dis[t = j]; 
15         vis[t] = 1;
16         for(int j = 1; j <= n; j++) dis[j] = min(dis[j], dis[t] + g[t][j]);
17     }
18 }
19     
20 
21 int main(){
22     memset(g, 0x3f3f, sizeof(g));//初始化！！
23     scanf("%d%d%d%d", &n, &c, &ts, &te);
24     for(int i = 1; i <= c; i++){
25         int u, v, w;
26         scanf("%d%d%d", &u, &v, &w);
27         g[u][v] = g[v][u] = w;
28     }
29     dijkstra(ts);
30     printf("%d", dis[te]);
31     return 0;
32 }