首页 > 其他分享 >PTA | 天梯地图

PTA | 天梯地图

时间：2024-11-09 17:46:47浏览次数：3  
标签：currentI int top 地图 PTA length map1 天梯 time

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

输入格式

输入在第一行给出两个正整数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

思路

这道题，让人想到一个东西——动态规划。

截止到n个结点的时候走过的最短距离=min（上一次到达自己的最短路径，截止到n-1个结点的时候走过的最短距离+第n-1个结点到第n个结点的距离）

这时要创建这样的一个结构

int times[N+1];
int dis[N+1];
for(int i = 0; i < N; ++i) {
	dis[i] = times[i] = INT_MAX;
} 
int parent[N+1];

times是用来存储时间的，dis是用来存储距离的，parent是用来存储父节点的。

我们要创建一个队列，这个队列是用来存储当前的位置，当前的距离，当前的时间的。

struct currentPlace {
    int currentI;
    int length;
    int time;
};
queue<currentPlace> q;

对于得到的最短路径，我们要用一个parent来存储父节点，然后我们要用一个while循环来得到最短路径。

void findLength(int be, int en, int N) {
	int dis[N+1];
	for(int i = 0; i < N; ++i) {
		dis[i] = INT_MAX;
	} 
	int parent[N+1];
	queue<pair<int, int>> q;
	q.push({be, 0});
	parent[be] = -1;
	dis[be] = 0;
	while(!q.empty()) {
		pair<int, int> top = q.front();
		for(int i = 0; i < N; ++i) {
			if(map1[top.first][i].canGo && i != parent[top.first]) {
				if(dis[i] > top.second+map1[top.first][i].length) {
					dis[i] = top.second+map1[top.first][i].length;
					parent[i] = top.first;
					q.push({i, top.second+map1[top.first][i].length});
				}
			}
		}
		q.pop();
	}	
	for(int i = en; i != -1; i = parent[i]) {
		lengthdq.insert(lengthdq.begin(), i);
	}
	lowlength = dis[en];
}

对于得到的最快路径，我们要用一个parent来存储父节点，然后我们要用一个while循环来得到最快路径。

这个最快路径的判断条件是，如果时间小于times[i]，那么就更新times[i]，如果时间等于times[i]，那么就判断距离，如果距离小于dis[i]，那么就更新dis[i]。

void findTime(int be, int en, int N) {
    int times[N+1];
    int dis[N+1];
    for(int i = 0; i < N; ++i) {
        dis[i] = times[i] = INT_MAX;
    } 
    int parent[N+1];
    queue<currentPlace> q;
    q.push({be, 0, 0});
    parent[be] = -1;
    times[be] = dis[be] = 0;
    while(!q.empty()) {
        currentPlace top = q.front();
        for(int i = 0; i < N; ++i) {
            if(map1[top.currentI][i].canGo && i != parent[top.currentI]) {
                if(times[i] > top.time+map1[top.currentI][i].time) {
                    times[i] = top.time+map1[top.currentI][i].time;
                    parent[i] = top.currentI;
                    dis[i] = top.length+map1[top.currentI][i].length;
                    q.push({i, top.length+map1[top.currentI][i].length, top.time+map1[top.currentI][i].time});
                } else if(times[i] == top.time+map1[top.currentI][i].time) {
                    if(dis[i] > top.length+map1[top.currentI][i].length) {
                        dis[i] = top.length+map1[top.currentI][i].length;
                        parent[i] = top.currentI;
                        times[i] = top.time+map1[top.currentI][i].time;
                        q.push({i, top.length+map1[top.currentI][i].length, top.time+map1[top.currentI][i].time});
                    }
                }
            }
        }
        q.pop();
    }	
    for(int i = en; i != -1; i = parent[i]) {
        timedq.insert(timedq.begin(), i);
    }
    lowTime = times[en];
}

整个程序的思路

首先，我们要创建一个结构体，这个结构体是用来存储地图的。

struct node {
    int length;
    int time;
    bool canGo;
};

然后，我们要创建一个地图，这个地图是用来存储地图的。

node map1[510][510];

然后，我们要创建一个lengthdq和timedq，这个是用来存储最短路径和最快路径的。

vector<int> lengthdq, timedq;

然后，我们要创建一个lowTime和lowlength，这个是用来存储最短路径和最快路径的时间和距离。

int lowTime, lowlength;

然后，我们要创建一个findLength和findTime，这个是用来找到最短路径和最快路径的。

void findLength(int be, int en, int N) {
    int dis[N+1];
    for(int i = 0; i < N; ++i) {
        dis[i] = INT_MAX;
    }
    int parent[N+1];
    queue<pair<int, int>> q;
    q.push({be, 0});
    parent[be] = -1;
    dis[be] = 0;
    while(!q.empty()) {
        pair<int, int> top = q.front();
        for(int i = 0; i < N; ++i) {
            if(map1[top.first][i].canGo && i != parent[top.first]) {
                if(dis[i] > top.second+map1[top.first][i].length) {
                    dis[i] = top.second+map1[top.first][i].length;
                    parent[i] = top.first;
                    q.push({i, top.second+map1[top.first][i].length});
                }
            }
        }
        q.pop();
    }
    for(int i = en; i != -1; i = parent[i]) {
        lengthdq.insert(lengthdq.begin(), i);
    }
    lowlength = dis[en];
}

void findTime(int be, int en, int N) {
    int times[N+1];
    int dis[N+1];
    for(int i = 0; i < N; ++i) {
        dis[i] = times[i] = INT_MAX;
    }
    int parent[N+1];
    queue<currentPlace> q;
    q.push({be, 0, 0});
    parent[be] = -1;
    times[be] = dis[be] = 0;
    while(!q.empty()) {
        currentPlace top = q.front();
        for(int i = 0; i < N; ++i) {
            if(map1[top.currentI][i].canGo && i != parent[top.currentI]) {
                if(times[i] > top.time+map1[top.currentI][i].time) {
                    times[i] = top.time+map1[top.currentI][i].time;
                    parent[i] = top.currentI;
                    dis[i] = top.length+map1[top.currentI][i].length;
                    q.push({i, top.length+map1[top.currentI][i].length, top.time+map1[top.currentI][i].time});
                } else if(times[i] == top.time+map1[top.currentI][i].time) {
                    if(dis[i] > top.length+map1[top.currentI][i].length) {
                        dis[i] = top.length+map1[top.currentI][i].length;
                        parent[i] = top.currentI;
                        times[i] = top.time+map1[top.currentI][i].time;
                        q.push({i, top.length+map1[top.currentI][i].length, top.time+map1[top.currentI][i].time});
                    }
                }
            }
        }
        q.pop();
    }
    for(int i = en; i != -1; i = parent[i]) {
        timedq.insert(timedq.begin(), i);
    }
    lowTime = times[en];
}

然后，我们要输入地图的信息。

int N, M, A, B, length, time, oneWay, be, en;
cin >> N >> M;
for(int i = 1; i <= M; ++i) {
    cin >> A >> B  >> oneWay >> length >> time;
    if(oneWay == 0) {
        map1[B][A].length = map1[A][B].length = length;
        map1[B][A].time = map1[A][B].time = time;
        map1[B][A].canGo = map1[A][B].canGo = true;
    } else {
        map1[A][B].length = length;
        map1[A][B].time = time;
        map1[A][B].canGo = true;
    }
}
cin >> be >> en;
findLength(be, en, N);
findTime(be, en, N);

然后，判断两个路径是否相同，如果相同，就输出Time = T; Distance = D: 起点 => 节点1 => ... => 终点，否则，就输出Time = T: 起点 => 节点1 => ... => 终点和Distance = D: 起点 => 节点1 => ... => 终点。

int flag = 0;
for(int i = 0; i < timedq.size() && i < lengthdq.size(); ++i) {
    if(timedq[i] != lengthdq[i]) {
        flag = 1;
    }
}
if(flag == 0) {
    cout << "Time = " << lowTime << "; ";
    cout << "Distance = " << lowlength << ": ";
    int f = 0;
    for(auto i: lengthdq) {
        if(f == 0) {
            cout << i;
            f = 1;
        } else 
            cout << " => " << i;
    }
} else {
    cout << "Time = " << lowTime << ": ";
    int f = 0;
    for(auto i: timedq) {
        if(f == 0) {
            cout << i;
            f = 1;
        } else 
            cout << " => " << i;
    }
    cout << endl;
    cout << "Distance = " << lowlength << ": ";
    f = 0;
    for(auto i: lengthdq) {
        if(f == 0) {
            cout << i;
            f = 1;
        } else 
            cout << " => " << i;
    }
}

当然，在这种情况下，我们不使用isGone来判断是否走过，而是判断i != parent[top.first]来判断是否走过。

if(map1[top.first][i].canGo && i != parent[top.first])

Code

#include <bits/stdc++.h>
using namespace std;

struct node {
	int length;
	int time;
	bool canGo;
};

struct currentPlace {
	int currentI;
	int length;
	int time;
};

vector<int> lengthdq, timedq;
int lowTime, lowlength;

node map1[510][510];

void findLength(int be, int en, int N) {
	int dis[N+1];
	for(int i = 0; i < N; ++i) {
		dis[i] = INT_MAX;
	} 
	int parent[N+1];
	queue<pair<int, int>> q;
	q.push({be, 0});
	parent[be] = -1;
	dis[be] = 0;
	while(!q.empty()) {
		pair<int, int> top = q.front();
		for(int i = 0; i < N; ++i) {
			if(map1[top.first][i].canGo && i != parent[top.first]) {
				if(dis[i] > top.second+map1[top.first][i].length) {
					dis[i] = top.second+map1[top.first][i].length;
					parent[i] = top.first;
					q.push({i, top.second+map1[top.first][i].length});
				}
			}
		}
		q.pop();
	}	
	for(int i = en; i != -1; i = parent[i]) {
		lengthdq.insert(lengthdq.begin(), i);
	}
	lowlength = dis[en];
}

void findTime(int be, int en, int N) {
	int times[N+1];
	int dis[N+1];
	for(int i = 0; i < N; ++i) {
		dis[i] = times[i] = INT_MAX;
	} 
	int parent[N+1];
	queue<currentPlace> q;
	q.push({be, 0, 0});
	parent[be] = -1;
	times[be] = dis[be] = 0;
	while(!q.empty()) {
		currentPlace top = q.front();
		for(int i = 0; i < N; ++i) {
			if(map1[top.currentI][i].canGo && i != parent[top.currentI]) {
				if(times[i] > top.time+map1[top.currentI][i].time) {
					times[i] = top.time+map1[top.currentI][i].time;
					parent[i] = top.currentI;
					dis[i] = top.length+map1[top.currentI][i].length;
					q.push({i, top.length+map1[top.currentI][i].length, top.time+map1[top.currentI][i].time});
				} else if(times[i] == top.time+map1[top.currentI][i].time) {
					if(dis[i] > top.length+map1[top.currentI][i].length) {
						dis[i] = top.length+map1[top.currentI][i].length;
						parent[i] = top.currentI;
						times[i] = top.time+map1[top.currentI][i].time;
						q.push({i, top.length+map1[top.currentI][i].length, top.time+map1[top.currentI][i].time});
					}
				}
			}
		}
		q.pop();
	}	
	for(int i = en; i != -1; i = parent[i]) {
		timedq.insert(timedq.begin(), i);
	}
	lowTime = times[en];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int N, M, A, B, length, time, oneWay, be, en;
	cin >> N >> M;
	for(int i = 1; i <= M; ++i) {
		cin >> A >> B  >> oneWay >> length >> time;
		if(oneWay == 0) {
			map1[B][A].length = map1[A][B].length = length;
			map1[B][A].time = map1[A][B].time = time;
			map1[B][A].canGo = map1[A][B].canGo = true;
		} else {
			map1[A][B].length = length;
			map1[A][B].time = time;
			map1[A][B].canGo = true;
		}
	}
	cin >> be >> en;
	findLength(be, en, N);
	findTime(be, en, N);
	int flag = 0;
	for(int i = 0; i < timedq.size() && i < lengthdq.size(); ++i) {
		if(timedq[i] != lengthdq[i]) {
			flag = 1;
		}
	}
	if(flag == 0) {
		cout << "Time = " << lowTime << "; ";
		cout << "Distance = " << lowlength << ": ";
		int f = 0;
		for(auto i: lengthdq) {
			if(f == 0) {
				cout << i;
				f = 1;
			} else 
				cout << " => " << i;
		}
	} else {
		cout << "Time = " << lowTime << ": ";
		int f = 0;
		for(auto i: timedq) {
			if(f == 0) {
				cout << i;
				f = 1;
			} else 
				cout << " => " << i;
		}
		cout << endl;
		cout << "Distance = " << lowlength << ": ";
		f = 0;
		for(auto i: lengthdq) {
			if(f == 0) {
				cout << i;
				f = 1;
			} else 
				cout << " => " << i;
		}
	}
}

标签：currentI,int,top,地图,PTA,length,map1,天梯,time
From： https://blog.csdn.net/qq_21739599/article/details/143647475

相关文章

  • PTA||7-2 求最大值及其下标（第九周）
    本题要求编写程序，找出给定的n个数中的最大值及其对应的最小下标（下标从0开始）。输入格式:输入在第一行中给出一个正整数n（1<n≤10）。第二行输入n个整数，用空格分开。输出格式:在一行中输出最大值及最大值的最小下标，中间用一个空格分开。输入样例:628101910输出样例:10......
  • 学习笔记（三十）：ArkUi-UIContext.getPromptAction(弹窗)
    概述：基于promptAction弹窗演进而来，支持全局自定义弹窗，不依赖UI组件，依赖UIContext，支持在非页面文件中使用，弹窗内容支持动态修改，支持自定义弹窗圆角半径、大小和位置，适合在与页面解耦的全局弹窗、自定义弹窗显示和退出动画等场景下使用。注意：需先使用UIContext中的getPromptAct......
  • 解决微信小程序地图callout气泡在ios展示，在安卓机不展示
    前段时间和小伙伴们接了一个租房小程序的单子，其中有个地图找房功能，项目已经交付了一一段时间，由于我们和客户都没有安卓机，于是在地图有个bug我们都没发现。    bug复现:我们使用了小程序的marker标记点用于标记展示，由于有个自带的小图标，我们用不上自带的小图标，于是直接a......
  • Java复习39（PTA)
    出勤统计分数15全屏浏览切换布局作者 大数据2021单位 山东科技大学某公司现需要统计员工出勤次数，具体要求如下：输入样例:MarkTomIvorMarkIvorMarkJackend输入样例解释:每行表示某天出勤的员工名单，以空格间隔。end表示输入结束输出样例:Mark3Ivor2......
  • KITTI_00_SPTAM轨迹和KITTI_00_ORB轨迹
    KITTI_00_SPTAM轨迹和KITTI_00_ORB轨迹分别代表什么KITTI_00_SPTAM轨迹和KITTI_00_ORB轨迹分别代表的是两种不同的SLAM（SimultaneousLocalizationandMapping，即同时定位与建图）算法在KITTI数据集上生成的轨迹估计结果。1.KITTI_00_SPTAM轨迹：这代表了S-PTAM（Stereo......
  • 我的世界(Minecraft)_游戏地图的生成
    相关：HowMinecraftACTUALLYWorks......
  • 绞尽脑汁终于搞定/天地图标注点marker旋转/任意角度旋转/无需引入其他框架
    一、前言说明在其他地图组件中，标注点marker都是可以设置旋转角度的，这个功能其实非常实用，比如飞机移动轨迹，就是需要旋转飞机头飞行，轮船轨迹移动也是，百度地图和腾讯地图是通过调用setRotation函数设置，高德地图是setAngle，唯独天地图没有提供对应接口，找遍了文档和源码，也没有找到对应......
  • vue实现天地图电子围栏
    一、文档vue3javascriptWGS84、GCj02相互转换天地图官方文档注册登录然后申请应用key，通过CDN引入<scriptsrc="http://api.tianditu.gov.cn/api?v=4.0&tk=您的密钥"type="text/javascript"></script>二、分析所谓电子围栏1、就是在地图商通过经纬度将点标注出......
  • 基于Java+SpringBoot+Vue+HTML5旅游网站(源码+LW+调试文档+讲解等)/旅游攻略/旅游指南
    博主介绍......
  • 地图框架之mapbox——（三）
    一、加载点数据到地图上1、准备一个点数据vardata={type:"FeatureCollection",features:[{type:"Feature",geometry:{type:"Point",coordinates:[114.30,30.50]}}]}2、创建地图并加载这个点，上面是yid......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99