PTA天梯 L3-007 天梯地图

柔情只为你懂 2021-12-20 06:15 425阅读 0赞

## L3-007 天梯地图 ##

### 题目： ###

本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

#### 输入格式： ####

输入在第一行给出两个正整数`N`（2 ≤ `N` ≤ 500）和`M`，分别为地图中所有标记地点的个数和连接地点的道路条数。随后`M`行，每行按如下格式给出一条道路的信息：

V1 V2 one-way length time

其中`V1`和`V2`是道路的两个端点的编号（从0到`N`\-1）；如果该道路是从`V1`到`V2`的单行线，则`one-way`为1，否则为0；`length`是道路的长度；`time`是通过该路所需要的时间。最后给出一对起点和终点的编号。

#### 输出格式： ####

首先按下列格式输出最快到达的时间`T`和用节点编号表示的路线：

Time = T: 起点 => 节点1 => ... => 终点

然后在下一行按下列格式输出最短距离`D`和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => ... => 终点

如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => ... => 终点

#### 输入样例1： ####

10 15
    0 1 0 1 1
    8 0 0 1 1
    4 8 1 1 1
    5 4 0 2 3
    5 9 1 1 4
    0 6 0 1 1
    7 3 1 1 2
    8 3 1 1 2
    2 5 0 2 2
    2 1 1 1 1
    1 5 0 1 3
    1 4 0 1 1
    9 7 1 1 3
    3 1 0 2 5
    6 3 1 2 1
    5 3

#### 输出样例1： ####

Time = 6: 5 => 4 => 8 => 3
    Distance = 3: 5 => 1 => 3

#### 输入样例2： ####

7 9
    0 4 1 1 1
    1 6 1 3 1
    2 6 1 1 1
    2 5 1 2 2
    3 0 0 1 1
    3 1 1 3 1
    3 2 1 2 1
    4 5 0 2 2
    6 5 1 2 1
    3 5

#### 输出样例2： ####

Time = 3; Distance = 4: 3 => 2 => 5

### **解题思路：** ###

首先是建图，然后求两次最短路径。

因为求最快的路时要用到最短的路，所以先求最短的路，再求最快的路。

用pre记录每个节点的上一个节点来记录路径。

用到的是 图的最短路径算法，这里用的是dijkstra算法。

### **代码：** ###

起点Start，Len\[k\]表示从start到k的最短路径，用preL\[k\]记录k的前驱点。

根据题意，变异dijkstra算法：如果最快到达路线不唯一，则输出几条最快路线中最短的那条。如果最短距离的路线不唯一，则输出途径节点数最少的那条。

1 #include <cstdio>
      2 #include <cstring>
      3 #include <stack>
      4 #include <iostream>
      5 #include <algorithm>
      6 #define N 505
      7 using namespace std;
      8 
      9 int maxint = 9999999;
     10 int n, Start, End, i, j;
     11 bool vis[N];    //标记是否访问过
     12 int mapL[N][N];    //记录距离的伴随矩阵
     13 int mapT[N][N];    //记录时间的伴随矩阵
     14 int Len[N];        //Start到k 的最短距离
     15 int Time[N];    //Start到k 的最少时间
     16 int preL[N];    //最短距离路径前驱
     17 int preT[N];    //最少时间路径前驱
     18 
     19 //Dijstra算法求最短距离，修改后以符合题意
     20 void Dijstra_Len(){
     21     int step[N];
     22     memset(step, 0, sizeof(step));
     23     step[Start] = 1;
     24     //step记录节点数
     25     memset(vis, 1, sizeof(vis));
     26     Len[Start] = 0;
     27     while(1){
     28         int minl = maxint, k;
     29         //在没有被访问过的点中找一个顶点k,使len[k]最小
     30         for(i = 0;i < n; i++){
     31             if(vis[i] && minl > Len[i]){
     32                 minl = Len[i];
     33                 k = i;
     34             }
     35         }
     36         //如果所有点都已经访问过，则结束遍历
     37         if(minl == maxint)break;
     38         //顶点k 标记为已确定（start 到达k 的最短路径）
     39         vis[k] = 0;
     40         //遍历与k 相连的每个未确定最短路径的顶点j
     41         for(i = 0;i < n; i++){
     42             int d = Len[k] + mapL[k][i];
     43             if(vis[i] && Len[i] > d){
     44                 Len[i] = d;
     45                 preL[i] = k;
     46                 step[i] = step[k]+1;
     47             //当路径距离相等时，优先记录节点数少的路径
     48             }else if(vis[i] && Len[i] == d && step[k]+1 < step[i]){
     49                 preL[i] = k;
     50                 step[i] = step[k]+1;
     51             }
     52         }
     53     }
     54 }
     55 
     56 //Dijstra算法求最少时间，修改后以符合题意
     57 void Dijstra_Time(){
     58     memset(vis, 1, sizeof(vis));
     59     //用于记录距离长度
     60     int dis[N];
     61     for(i = 0;i < n; i++)
     62         dis[i] = mapL[Start][i];
     63     Time[Start] = 0;
     64     dis[Start] = 0;
     65     while(1){
     66         int minl = maxint, k;
     67         for(i = 0;i < n; i++){
     68             if(vis[i] && minl > Time[i]){
     69                 minl = Time[i];
     70                 k = i;
     71             }
     72         }
     73         if(minl == maxint)break;
     74         vis[k] = 0;
     75         for(i = 0;i < n; i++){
     76             int t = Time[k]+mapT[k][i];
     77             int d = dis[k]+mapL[k][i];
     78             if(vis[i] && Time[i] > t){
     79                 dis[i] = d;
     80                 Time[i] = t;
     81                 preT[i] = k;
     82             //当时间相同时，保存其中距离最短的
     83             }else if(vis[i] && Time[i] == t && dis[i] > d){
     84                 dis[i] = d;
     85                 preT[i] = k;
     86             }
     87         }
     88     }
     89 }
     90 
     91 int main(){
     92     memset(preL, -1, sizeof(preL));
     93     memset(preT, -1, sizeof(preT));
     94     int m;
     95     cin >> n >> m;
     96     for(i = 0;i < n; i++){
     97         Len[i] = maxint;
     98         Time[i] = maxint;
     99         for(int j = 0;j < n;++j){
    100             mapL[i][j] = maxint;
    101             mapT[i][j] = maxint;
    102         }
    103     }
    104     while(m--){
    105         int x, y, t;
    106         cin >> x >> y >> t;
    107         cin >> mapL[x][y] >> mapT[x][y];
    108         if(!t){
    109             mapL[y][x] = mapL[x][y];
    110             mapT[y][x] = mapT[x][y];
    111         }
    112     }
    113     cin >> Start >> End;
    114     Dijstra_Len();
    115     Dijstra_Time();
    116     //取出前驱节点里保存的路径，装入stack中
    117     stack<int> bestT, bestL;
    118     i = End;
    119     while(i != Start){
    120         bestT.push(i);
    121         i = preT[i];
    122     }
    123     i = End;
    124     while(i != Start){
    125         bestL.push(i);
    126         i = preL[i];
    127     }
    128     //按题意要求输出
    129     if(bestL == bestT){
    130         printf("Time = %d; Distance = %d: %d",Time[End], Len[End], Start);
    131         while(!bestL.empty()){
    132             int t = bestL.top();
    133             cout << " => " << t;
    134             bestL.pop();
    135         }cout << endl;
    136     }else {
    137         cout << "Time = " << Time[End] << ": " << Start;
    138         while(!bestT.empty()){
    139             int t = bestT.top();
    140             cout << " => " << t;
    141             bestT.pop();
    142         }
    143         cout << endl << "Distance = " << Len[End] << ": " << Start;
    144         while(!bestL.empty()){
    145             int t = bestL.top();
    146             cout << " => " << t;
    147             bestL.pop();
    148         }cout << endl;
    149     }
    150 
    151     return 0;
    152 }

转载于:https://www.cnblogs.com/AardWolf/p/10623411.html