题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805464397627392
这题挺经典的，可以用来熟悉Dijkstra算法

代码

纯Dijkstra算法

  1. #include<algorithm>
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<vector>
  5. using namespace std;
  6. const int maxn = 510;
  7. const int inf = 0x3fffffff;
  9. int n, m, st, ed;
  10. int G[maxn][maxn], cost[maxn][maxn], pre[maxn], d[maxn], c[maxn];
  11. bool vis[maxn] = {false};
  13. void Dijkstra(int s){
  14.     fill(d, d + maxn, inf);
  15.     fill(c, c + maxn, inf);
  16.     d[s] = 0;
  17.     c[s] = 0;
  18.     for(int i = 0; i < n; i++) pre[i] = i;
  19.     for(int i = 0 ; i < n; i++){
  20.         int u = -1, min = inf;
  21.         for(int j = 0; j < n; j++){
  22.             if(vis[j] == false && d[j] < min){
  23.                 u = j;
  24.                 min = d[j];
  25.             }
  26.         }
  27.         if(u == -1) return;
  28.         vis[u] = true;
  29.         for(int v = 0; v < n; v++){
  30.             if(vis[v] == false && G[u][v] != inf){
  31.                 if(G[u][v] + d[u] < d[v]){
  32.                     d[v] = G[u][v] + d[u];
  33.                     c[v] = cost[u][v] + c[u];
  34.                     pre[v] = u;
  35.                 } else if(d[v] == G[u][v] + d[u]){
  36.                     if(c[v] > cost[u][v] + c[u]){
  37.                         c[v] = cost[u][v] + c[u];
  38.                         pre[v] = u;
  39.                     }
  40.                 }
  41.             }
  42.         }
  43.     }
  44. }
  46. void DFS(int v){
  47.     if(v == st){
  48.         printf("%d ", v);
  49.         return;
  50.     }
  51.     DFS(pre[v]);
  52.     printf("%d ",v);
  53. }
  55. int main(){
  56.     scanf("%d%d%d%d", &n, &m, &st, &ed);
  57.     int c1, c2, temp_d, temp_c;
  58.     fill(G[0], G[0] + maxn * maxn, inf);
  59.     for(int i = 0; i < m; i++){
  60.         scanf("%d%d%d%d", &c1, &c2, &temp_d, &temp_c);
  61.         G[c1][c2] = G[c2][c1] = temp_d;
  62.         cost[c1][c2] = cost[c2][c1] = temp_c;
  63.     }
  64.     Dijkstra(st);
  65.     DFS(ed);
  66.     printf("%d %d\n", d[ed], c[ed]);
  67.     return 0;
  68. }

Dijkstra + DFS

感觉用不太上，熟悉第一种写法就够了.jpg 注意DFS函数的写法！！！

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<vector>
  4. #include<algorithm>
  5. using namespace std;
  6. const int maxn = 510;
  7. const int inf = 1000000000;
  9. int n, m, st, ed, G[maxn][maxn], cost[maxn][maxn];
  10. int d[maxn], minCost = inf;
  11. bool vis[maxn] = {false};
  12. vector<int> pre[maxn];
  13. vector<int> tempPath, path;
  15. void Dijkstra(int s){
  16.     fill(d, d + maxn, inf);
  17.     d[s] = 0;
  18.     for(int i = 0 ; i < n; i++){
  19.         int u = -1, min = inf;
  20.         for(int j = 0; j < n; j++){
  21.             if(vis[j] == false && d[j] < min){
  22.                 u = j;
  23.                 min = d[j];
  24.             }
  25.         }
  26.         if(u == -1)return;
  27.         vis[u] = true;
  28.         for(int v = 0; v < n; v++){
  29.             if(vis[v] == false && G[u][v] != inf){
  30.                 if(d[v] > d[u] + G[u][v]){
  31.                     d[v] = d[u] + G[u][v];
  32.                     pre[v].clear();
  33.                     pre[v].push_back(u);
  34.                 } else if(d[v] == d[u] + G[u][v]){
  35.                     pre[v].push_back(u);
  36.                 }
  37.             }
  38.         }
  39.     }
  40. }
  42. void DFS(int v){
  43.     if(v == st){
  44.         tempPath.push_back(v);
  45.         int tempCost = 0;
  46.         for(int i = tempPath.size() - 1; i > 0; i--){
  47.             int id = tempPath[i], idNext = tempPath[i - 1];
  48.             tempCost += cost[id][idNext];
  49.         }
  50.         if(tempCost < minCost){
  51.             minCost = tempCost;
  52.             path = tempPath;
  53.         }
  54.         tempPath.pop_back();
  55.         return;
  56.     }
  57.     tempPath.push_back(v);
  58.     for(int i = 0; i < pre[v].size(); i++){
  59.         DFS(pre[v][i]);
  60.     }
  61.     tempPath.pop_back();
  62. }
  64. int main(){
  65.     scanf("%d%d%d%d", &n, &m, &st, &ed);
  66.     int c1, c2, temp_d, temp_c;
  67.     fill(G[0], G[0] + maxn * maxn, inf);
  68.     for(int i = 0; i < m; i++){
  69.         scanf("%d%d%d%d", &c1, &c2, &temp_d, &temp_c);
  70.         G[c1][c2] = G[c2][c1] = temp_d;
  71.         cost[c1][c2] = cost[c2][c1] = temp_c;
  72.     }
  73.     Dijkstra(st);
  74.     DFS(ed);
  75.     for(int i = path.size() - 1; i >= 0; i--){
  76.         printf("%d ", path[i]);
  77.     }
  78.     printf("%d %d\n", d[ed], minCost);
  79.     return 0;
  80. }