觉得不错还请点个赞
本题难点是存储上数据上
- 怎么存每一站信息
用
unordered_map<string,string>m
来记录每一个航班的地点
m["SFO"]="DFW"
表示有一个航班是从SFO
飞向DFW
- 怎么找到起始站
在输入的过程中记录哪些地点是某一次航班的目的地
unordered_set<string>in;
对于
SFO
飞向DFW
我们需要in.insert("DFW")
表示
DFW
是一个航班的目的地 也表示着DFW
一定不是起始地点
- 如何打印结果
找到起始地点 $q$以后只要
m[p]!=""
就说明$p$还有目的地就还要继续飞
#include<iostream>
#include<cstring>
#include<unordered_map>
#include<unordered_set>
using namespace std;
int T,n;
int main(){
cin>>T;
for(int t=1;t<=T;t++){
unordered_map<string,string>m;//记录每一张票的信息
unordered_set<string>in;//记录哪些站有前驱 用来后记找到起始地点
cin>>n;
for(int i=0;i<n;i++){
string start,end;
cin>>start>>end;
m[start]=end;
in.insert(end);
}
string q;
for(auto [start,v]:m)
if(!in.count(start)){//如果没有前驱 他就是起始站点
q=start;
break;
}
printf("Case #%d:",t);
while(m[q]!=""){
cout<<" "<<q<<"-"<<m[q];
q=m[q];
}
printf("\n");
}
return 0;
}
tql
Orz