<--
如果对你有帮助的话点个赞呗
<--
不喜欢的话请点个踩,并在评论区告诉我哪里需要改正!
行程排序题解
题目描述
玛丽需要从某地飞往另一目的地,由于没有直达飞机,所以需要在中途转很多航班。
例如:SFO -> DFW DFW -> JFK JFK -> MIA MIA -> ORD
。
显然旅途中不可能到同一中转城市两次或以上,因为这没有意义。
不幸的是,她将自己的机票的顺序搞乱了,将机票按乘坐顺序整理好对她来说不是一件容易的事。
请你帮助玛丽整理机票,使机票按正确顺序排列。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $N$。
接下来 $2N$ 行,每 $2$ 行一组,表示一张机票的信息,每行包含一个字符串,其中第一行表示出发地,第二行表示目的地。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y
,其中 $x$ 是组别编号(从 $1$ 开始),$y$ 是表示实际行程的机票列表,行程中的每个航段应以 source-destination
的形式输出,航段之间用空格隔开。
数据范围
$1≤T≤100$,
$1≤N≤10000$
输入样例
2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA
输出样例
Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD
算法
(遍历+存unordered_map) $O(T×N)$
由于对于每个行程,起点和终点都是用字符串表示的,所以用unordered_map<string, string>
的数据结构表示比较合适。(用map
也是可以的,但性能较差)
只需要在每次输入起点和终点时将终点存入以起点为 $key$ 的位置,
然后找到玛丽一开始所在的总起点,从那里开始遍历,便能得到玛丽的机票顺序。
时间复杂度
对于每个测试数据,时间复杂度是线性的,即 $O(N)$。
共有 $T$ 个测试数据,所以总时间复杂度为 $O(T×N)$。
C++ 代码
#include <cstdio>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int main(){
int T;
scanf("%d", &T);
for(int cases = 1; cases <= T; cases++){
int n;
scanf("%d", &n);
unordered_map<string, string> next; next.clear();//存储行程的起点、终点
vector<string> places; places.clear();//存储去过的地方
unordered_map<string, int> status; status.clear();
/*
如果i是某个行程的起点,status[i]++
如果i是某个行程的终点,status[i]--
这样能更加方便地找到起点
*/
for(int i = 0; i < n; i++){
string x, y;
cin >> x >> y;
next[x] = y;//存储行程
status[x]++;
status[y]--;
places.push_back(x);
}
string start;
for(auto i : places)
if(status[i] == 1){
/*
如果某个地点是一个行程的起点,
且不是任何一个行程的终点,
则那个地点一定是玛丽一开始所在的总起点
*/
start = i;
break;
}
printf("Case #%d: ", cases);
while(next[start] != ""){
cout << start << "-" << next[start] << " ";
start = next[start];
}
cout << endl;
}
return 0;
}
C++ 代码(无注释)
#include <cstdio>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
int main(){
int T;
scanf("%d", &T);
for(int cases = 1; cases <= T; cases++){
int n;
scanf("%d", &n);
unordered_map<string, string> next; next.clear();
vector<string> places; places.clear();
unordered_map<string, int> status; status.clear();
for(int i = 0; i < n; i++){
string x, y;
cin >> x >> y;
next[x] = y;
status[x]++;
status[y]--;
places.push_back(x);
}
string start;
for(auto i : places)
if(status[i] == 1){
start = i;
break;
}
printf("Case #%d: ", cases);
while(next[start] != ""){
cout << start << "-" << next[start] << " ";
start = next[start];
}
cout << endl;
}
return 0;
}
备注
这是我第二次发题解,如果喜欢请点个赞支持一下本蒟蒻,谢谢!