题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805523835109376

这题是传统单DFS算法的应用，直接在更新最短距离那一步把事情都做完。

代码

  1. #include<vector>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<iostream>
  5. using namespace std;
  6. const int maxn = 510;
  7. const int INF = 1000000000;
  8. int n, m, c1, c2;
  9. int temp_c1, temp_c2, temp_d;
  10. int weight[maxn], G[maxn][maxn];
  11. int d[maxn], num[maxn], w[maxn];//d[maxn]是起点到各点的最短距离
  12. bool vis[maxn] = {false};
  14. void Dijkstra(){
  15.     fill(d, d + maxn, INF);
  16.     fill(w, w + maxn, 0);
  17.     fill(num, num + maxn, 0);
  18.     d[c1] = 0;
  19.     w[c1] = weight[c1];
  20.     num[c1] = 1;
  21.     for(int i = 0; i < n; i++){//循环n次
  22.         int u = -1, min = INF;
  23.         for(int j = 0; j < n; j++){//找到最小的
  24.             if(vis[j] == false && d[j] < min){
  25.                 u = j;
  26.                 min = d[j];
  27.             }
  28.         }
  29.         if(u == -1) return;
  30.         //更新d[]
  31.         vis[u] = true;
  32.         for(int v = 0; v < n; v++){
  33.             if(vis[v] == false && G[u][v] != INF){//没被访问过且可达
  34.                 if(d[u] + G[u][v] < d[v]){
  35.                     d[v] = d[u] + G[u][v];
  36.                     num[v] = num[u];
  37.                     w[v] = w[u] + weight[v];
  38.                 } else if (d[u] + G[u][v] == d[v]){
  39.                     if(weight[v] + w[u] > w[v]){
  40.                         w[v] = w[u] + weight[v];
  41.                     }
  42.                     num[v] += num[u];
  43.                 }
  44.             }
  45.         }
  46.     }
  47. }
  49. int main(){
  50.     scanf("%d%d%d%d", &n, &m, &c1, &c2);
  51.     for(int i = 0; i < n; i++) scanf("%d", &weight[i]);
  52.     fill(G[0], G[0] + maxn * maxn, INF);
  53.     for(int i = 0; i < m; i++){
  54.         scanf("%d %d %d", &temp_c1, &temp_c2, &temp_d);
  55.         G[temp_c1][temp_c2] = temp_d;
  56.         G[temp_c2][temp_c1] = temp_d;
  57.     }
  58.     Dijkstra();
  59.     printf("%d %d",num[c2], w[c2]);
  60.     return 0;
  61. }