PTA天梯 L3-007 天梯地图

2024-01-12 20:43:34

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：

输出样例1：

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

输入样例2：

输出样例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 }

码农公寓