PAT（甲级）1111 Online Map (30point(s)) 最短路算法

布满荆棘的人生 2024-05-08 06:03 7阅读 0赞

##### 题目 #####

[题目链接][Link 1]

##### 思路 #####

**题目大意**：给一张图，注意有的边是有向的，有的是无向的；分别找出从起点到终点最短路径和最快路径；如果两个路径相同，只输出一次；  
首先来看题的要求，需要输出路径，那么需要用一个pre数组存储最终路径上每一个节点的前驱；  
由于要求最短路和最快路，所以需要两次Dijktras算法：在求最短路的过程中，由于可能会出现最短路相同的情况，所以需要维护一个花费时间最短的t数组（注意：这个最短时间并不是全局最短时间，只是在满足最短路的前提下的最短时间，一会计算最短时间时需要重新赋值）；  
接着再求一下最短时间，出现最短时间相同时，需要以经过的节点数作为第二标尺，和第一次类似；  
每次求出一个最短路径后就把路径保存在一个vector中，最后比较两次的路径是否相同即可；  
**注意**：求最短路找到中间结点u后，更新最短距离时一定要先判断能不能从u直接到v，在进行更新；

##### 代码 #####

#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <set>
    
    using namespace std;
    const int maxn = 510;
    const int inf = 1e9;
    int n, m, head, tail;
    int dis[maxn][maxn], times[maxn][maxn];
    int d[maxn], t[maxn], pre[maxn], vis[maxn], num[maxn];
    vector<int> v1, v2;//v1存最短路径，v2存最短时间
    
    void DijkDis(int head){
        
         //初始化
         fill(d, d + maxn, inf);
         fill(t, t + maxn, inf);
         fill(pre, pre + maxn, -1);
         fill(vis, vis + maxn, false);
         d[head] = 0, t[head] = 0;
         //循环n次
         for(int i = 0; i < n; i ++){
        
              int u = -1, minn = inf;
              //找到最近的点
              for(int j = 0; j < n; j ++){
        
                   if(vis[j] == false && d[j] < minn){
        
                        minn = d[j], u = j;
                   }
              }
              if(u == -1) break;
              //标记已看过
              vis[u] = true;
              //更新最短距离
              for(int v = 0; v < n; v ++){
        
                   //遍历与该点连着的点
                   if(dis[u][v] != inf && vis[v] == false){
        
                        //如果出现最短路径
                        if(dis[u][v] + d[u] < d[v]){
        
                             d[v] = dis[u][v] + d[u];
                             t[v] = t[u] + times[u][v];
                             pre[v] = u;
                        }
                        //如果出现相同的最短路径
                        else if(dis[u][v] + d[u] == d[v]){
        
                             if(t[u] + times[u][v] < t[v]){
        
                                  t[v] = t[u] + times[u][v];
                                  d[v] = dis[u][v] + d[u];
                                  pre[v] = u;
                             }
                        }
                   }
    
              }
         }
         return;
    }
    
    void DijkTime(int head){
        
         //初始化
         fill(t, t + maxn, inf);
         fill(pre, pre + maxn, -1);
         fill(vis, vis + maxn, false);
         fill(num, num + maxn, inf);
         num[head] = 0, t[head] = 0;
         //循环n次
         for(int i = 0; i < n; i ++){
        
              int u = -1, minn = inf;
              //找到最近的点
              for(int j = 0; j < n; j ++){
        
                   if(vis[j] == false && t[j] < minn){
        
                        minn = t[j], u = j;
                   }
              }
              if(u == -1) break;
              //标记已看过
              vis[u] = true;
              //更新最短距离
              for(int v = 0; v < n; v ++){
        
                   if(times[u][v] != inf && vis[v] == false){
        
                        //如果出现最快路径
                        if(times[u][v] + t[u] < t[v]){
        
                             t[v] = times[u][v] + t[u];
                             num[v] = num[u] + 1;
                             pre[v] = u;
                        }
                        //如果出现相同的时间最快路径
                        else if(times[u][v] + t[u] == t[v]){
        
                             if(num[u] + 1 < num[v]){
        
                                  t[v] = t[u] + times[u][v];
                                  num[v] = num[u] + 1;
                                  pre[v] = u;
                             }
                        }
                   }
              }
         }
         return;
    }
    
    void DFS(int tail, vector<int>& v){
        
         //保存路径
         while(pre[tail] != -1){
        
              v.push_back(tail);
              tail = pre[tail];
         }
         v.push_back(tail);
    }
    //输出路径
    void show(vector<int>& v){
        
         for(int i = v.size() - 1; i > 0; i --){
        
              printf("%d -> ", v[i]);
         }
         printf("%d\n", v[0]);
    }
    
    int main()
    {
        
         //初始化
         fill(dis[0], dis[0] + maxn * maxn, inf);
         fill(times[0], times[0] + maxn * maxn, inf);
         scanf("%d%d", &n, &m);
         int u, v, flag, len, b;
         for(int i = 0; i < m; i ++){
        
              scanf("%d%d%d%d%d", &u, &v, &flag, &len, &b);
              dis[u][v] = len, times[u][v] = b;
              //如果不是单行道
              if(flag == 0) {
        
                   dis[v][u] = len, times[v][u] = b;
              }
         }
         scanf("%d%d", &head, &tail);//读入起点终点
         DijkDis(head);
         DFS(tail, v1);
         DijkTime(head);
         DFS(tail, v2);
         if(v1 == v2){
        
              printf("Distance = %d; Time = %d: ", d[tail], t[tail]);
              show(v1);
         }
         else{
        
              printf("Distance = %d: ", d[tail]);
              show(v1);
              printf("Time = %d: ", t[tail]);
              show(v2);
         }
         system("pause");
         return 0;
    }

[Link 1]: https://pintia.cn/problem-sets/994805342720868352/problems/994805358663417856