wenbao与最短路dij

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 #define N 10000000
 7 int road[200][200], vis[200];
 8 int dij[200], n, m, start, l;
 9 
10 void Dij(){
11     int i, j, k, v, path;
12     memset(vis, 0, sizeof(vis));
13     for(i = 0; i < n; i++) dij[i]=road[start][i];
14     dij[start] = 0;
15     vis[start] = 1;
16     for(i = 0; i < n; i++){
17         path = N;
18         for(j = 0; j < n; j++){
19             if(!vis[j] && path > dij[j]){
20                 path = dij[j];
21                 v = j;
22             }
23         }
24         vis[v] = 1;
25         for(k = 0; k < n; k++){
26             if(!vis[k]) dij[k] = min(dij[k], dij[v]+road[v][k]);
27         }
28     }
29 }
30 
31 int main(){
32     int i, j, a, b, c;
33     while(scanf("%d%d", &n, &m) != EOF){
34         for(i = 0; i < n; i++){
35             for(j = 0; j < n; j++){
36                 if(i==j) road[i][j] = road[j][i] = 0;
37                 else road[i][j] = road[j][i] = N;
38             }
39         }
40         for(i = 0; i < m; i++){
41             scanf("%d%d%d", &a, &b, &c);
42             road[a][b] = road[b][a] = min(road[a][b], c);
43         }
44         scanf("%d%d", &start, &l);
45         Dij();
46         if(dij[l] < N) printf("%d\n", dij[l]);
47         else printf("-1\n");
48     }
49     return 0;
50 }

 1 #include <iostream>
 2 #include <string.h>
 3 #include <queue>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int INF = 1e9;
 8 const int maxn = 209;
 9 const int maxr = 2009;
10 bool vis[maxn];
11 int dis[maxn], to[maxr], w[maxr], p[maxn], pre[maxr], index;
12 
13 struct Node{
14     int x, y;
15     bool friend operator < (Node a, Node b){
16         if(a.y == b.y) return a.x < b.x;
17         return a.y > b.y;
18     }
19 };
20 
21 void init(int x){
22     index = 1;
23     for(int i = 0; i <= x; ++i){
24         vis[i] = false, dis[i] = INF;
25         p[i] = 0;
26     }
27 }
28 
29 void Dij(int sta, int end){
30     priority_queue<Node> pq;
31     Node a, b;
32     a.x = sta, a.y = 0;
33     dis[sta] = 0;
34     pq.push(a);
35     while(!pq.empty()){
36         b = pq.top(); pq.pop();
37         int xx = b.x;
38         if(vis[xx]) continue;
39         vis[xx] = true;
40         for(int i = p[xx]; i; i = pre[i]){
41             int xxx = to[i];
42             if(!vis[xxx] && dis[xxx] > dis[xx] + w[i]){
43                 dis[xxx] = dis[xx] + w[i];
44                 a.x = xxx, a.y = dis[xxx];
45                 pq.push(a);
46             }
47         }
48     }
49     printf("%d\n", dis[end] == INF ? -1 : dis[end]);
50 }
51 
52 int main(){
53     int n, m, s, t, x, y, z;
54     while(~scanf("%d%d", &n, &m)){
55         init(n);
56         while(m--){
57             scanf("%d%d%d", &x, &y, &z);
58             to[index] = y, w[index] = z, pre[index] = p[x], p[x] = index++;
59             to[index] = x, w[index] = z, pre[index] = p[y], p[y] = index++;
60         }
61         scanf("%d%d", &s, &t);
62         Dij(s, t);
63     }
64     return 0;
65 }

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 #define INF 0xfffffff
 7 #define maxn 1000
 8 
 9 int road[1000][1000], dij[maxn], money[1000][1000], dijm[maxn];
10 bool flag[maxn];
11 
12 void Dij(int start, int endn, int n){
13     memset(flag, 0, sizeof(flag));
14     int path, v;
15     for(int i = 1; i <= n; i++){
16         dij[i] = road[start][i];
17         dijm[i] = money[start][i];
18     }
19     flag[start] = 1;
20     dij[start] = 0;
21     for(int i = 1; i <= n; i++){
22         path = INF;
23         for(int j = 1; j <= n; j++){
24             if(!flag[j] && path > dij[j]){
25                 path = dij[j];
26                 v = j;
27             }
28         }
29         flag[v] = 1;
30         for(int k = 1; k <= n; k++){
31             if(!flag[k]){
32                 if(dij[k] == dij[v] + road[v][k]){
33                     if(dijm[k] > dijm[v] + money[v][k]){
34                         dij[k] = dij[v] + road[v][k];
35                         dijm[k] = dijm[v] + money[v][k];
36                     }
37                 }
38                 else if(dij[k] > dij[v] + road[v][k]){
39                     dij[k] = dij[v] + road[v][k];
40                     dijm[k] = dijm[v] + money[v][k];
41                 }
42             }
43         }
44     }
45 }
46 
47 int main(){
48     int a, b, c, d, start, endn, n, m;
49     while(scanf("%d%d", &n, &m), n+m){
50         for(int i = 1; i <= n; i++){
51             for( int j = 1; j < i; j++){
52                 road[i][j]=road[j][i]= money[i][j]=money[j][i]=INF;
53             }
54         }
55         for(int i = 0; i < m ; i++){
56             scanf("%d%d%d%d", &a, &b, &c, &d);
57             if(road[a][b] > c){
58                 road[a][b] = road[b][a] = c;
59                 money[a][b] = money[b][a] = d;
60             }
61         }
62         scanf("%d%d", &start, &endn);
63         Dij(start, endn, n);
64         printf("%d %d\n",dij[endn], dijm[endn]);
65     }
66     return 0;
67 }