7-35 城市间紧急救援 (25分)-dijkstra最短路径

  1 #include <iostream>
  2 #define infinity 65535
  3 using namespace std;
  4 int cnt[1000];//S到某点最短路径的数目
  5 int low[1000];//S到某点最短路径长度
  6 int high[1000] = { 0 };//储存最短路径中前一结点救援队集结数的最大值
  7 int weight[1000];//某结点集结队数目
  8 int g[1000][1000];
  9 int front[1000];//最短路径中前驱结点
 10 int final[1000] = { 0 };//某结点是否处理完毕，处理完置1
 11 int N, M, S, D;
 12 void print();    
 13 int main()
 14 {
 15     cin >> N >> M >> S >> D;
 16         for(int i=0;i<N;i++)cnt[i]=1;
 17         /*cnt需要初始化为1，因为当没有其他最短路径的时候，cnt的值没有机会被修改，
 18         也就是默认值，那么就应该为1,不应初始化为0*/
 19     for (int i = 0; i < N; i++)
 20     {
 21         for (int j = 0; j < N; j++)
 22         {
 23             g[i][j] = infinity;
 24         }
 25         low[i] = infinity;
 26     }
 27     for (int i = 0; i < N; i++)
 28         cin >> weight[i];
 29     for (int i = 0; i < M; i++)
 30     {
 31         int a, b, c;
 32         cin >> a >> b >> c;
 33         g[a][b] = g[b][a] = c;
 34     }
 35     for (int i = 0; i < N; i++)
 36     {
 37         low[i] = g[0][i];
 38     }
 39     for (int i = 0; i < N; i++)
 40     {
 41         if (g[S][i] != infinity)
 42         {
 43             low[i] = g[S][i];
 44             front[i] = S;
 45             high[i] = weight[S];
 46         }
 47     }
 48     front[S] = -1;
 49     final[S] = 1;
 50     low[S] = 0;
 51     int k;
 52 //以下是dijkstra算法的实现
 53     for (int i = 0; i < N; i++)
 54     {
 55         int min = infinity;
 56         for (int j = 0; j < N; j++)
 57         {
 58             if (low[j] < min && !final[j])
 59             {
 60                 min = low[j];
 61                 k = j;
 62             }
 63         }
 64         high[k] = high[front[k]] + weight[front[k]];
 65         final[k] = 1;
 66         for (int w = 0; w < N; w++)
 67         {
 68             if (!final[w] && min + g[k][w] < low[w])
 69             {
 70                 cnt[w]=cnt[k];
 71                 low[w] = min + g[k][w];
 72                 front[w] = k;
 73                 high[w] = high[k] + weight[k];
 74             }
 75             else if (!final[w] && min + g[k][w] == low[w])/*else不能漏掉，因为low[w]在上一步改变了，有可能上下两个条件都符合，就会出现错误*/
 76             {
 77                 cnt[w]+=cnt[k];//即使权值没有比原来大，也需要增加最短路径数
 78                 if(high[k] + weight[k] > high[w])
 79                 {
 80                     front[w] = k;
 81                     high[w] = high[k] + weight[k];
 82                 }
 83             }
 84         }
 85     }
 86     print();
 87     return 0;
 88 }
 89 void print()
 90 {    
 91     cout << cnt[D]<<' ';
 92     cout << high[D]+weight[D] << endl;
 93     int s[1000];
 94     int r=-1;
 95     while (D!=-1)//需要利用堆栈输出
 96     {
 97         s[++r] = D;
 98         D = front[D];
 99     }
100     while (r != -1)
101     {//注意处理最后面的空格
102         if (r == 0)cout << s[r--];
103         else cout << s[r--] << ' ';
104     }
105 }