title: PAT1131
date: 2021-01-22 20:03:07
tags: PAT
1131
题目：
给出最短的乘车路径
范围：
- <=100条线路
- 每条线路站数<=100
- <=10000个点
- 点的度数<=5
- 查询路径数<=10
分析：
- 要求路径，所以需要记录路径
- 求的是单点对单点的路径，所以使用DFS/BFS
- 由于要求最短的路径，采用BFS
- 要记录到某点的最短路径，记录内容：路径全部 / 到达点
- 图的保存内容：边集，点集
解法:
由于使用纯粹的BFS设计开始出了问题，后来参照网上的方式：先BFS找长度上限，再使用DFS配合路径长度剪枝找路径
找路径的过程中，我采用的存储方式是前向查找，也就是存储来的节点，但是后来输出就需要一个栈来保存逆序
实际上存储仍然可以使用前向查找，但是可以换成查找目标到起始的方式，就可以少一步了
同时DFS时需要更新节点的来向，如果能够使 站数 和 换乘数 减少，我们就更新节点信息，直到合适距离的找完
代码:
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <stack>
#define INF 0x7fffffff
using namespace std;
struct way
{
/* data */
string from;
int line_num;
int cost;
int line_cost;
};
struct plan
{
/* data */
string from;
string to;
int line;
};
map<string, map<string, int> *> subway_map;
map<string, way> line;
stack<plan> plan_way;
string from_station[15], to_station[15];
int BFS(string from, string to){
queue<string> BFS;
set<string> getted ;
int depth = -1;
BFS.push(from);
while(!BFS.empty()){
int num_BFS = BFS.size();
for(int i = 0; i < num_BFS; i++){
string tmp = BFS.front();
BFS.pop();
getted.insert(tmp);
BFS.push(tmp);
}
for(int i = 0; i < num_BFS; i++){
string tmp = BFS.front();
BFS.pop();
map<string, int> * station = subway_map[tmp];
for(map<string, int>::iterator iter = station->begin(); iter != station->end(); iter++){
if(getted.count(iter->first) == 0){
BFS.push(iter->first);
}
}
}
depth++ ;
if(getted.count(to) != 0) break;
}
return depth;
}
void DFS(string from, string to, int depth){
stack<string> DFS;
DFS.push(from);
map<string, way> line_tmp = line;
line_tmp[from].cost = 0;
line_tmp[from].line_num = 0;
line_tmp[from].from = "0";
while(!DFS.empty()){
// for(map<string, way>::iterator iter=line_tmp.begin(); iter != line_tmp.end(); iter++){
// cout<<iter->first<<" From : "<<iter->second.from<<" by : "<<iter->second.line_num<<" cost : "<<iter->second.line_cost<<endl;
// }
// cout<<endl;
string cur = DFS.top();
DFS.pop();
if(line_tmp[cur].cost == depth) continue;
// else if(cur == to) break ;
else {
map<string, int> * station = subway_map[cur];
for(map<string, int>::iterator iter = station->begin(); iter != station->end(); iter++){
if(line_tmp[iter->first].cost > line_tmp[cur].cost + 1){
DFS.push(iter->first);
line_tmp[iter->first].cost = line_tmp[cur].cost + 1;
line_tmp[iter->first].line_num = iter->second;
line_tmp[iter->first].from = cur;
if(iter->second == line_tmp[cur].line_num) line_tmp[iter->first].line_cost = line_tmp[cur].line_cost;
else line_tmp[iter->first].line_cost = line_tmp[cur].line_cost+1;
}
else if(line_tmp[iter->first].cost == line_tmp[cur].cost + 1){
if(iter->second == line_tmp[cur].line_num && line_tmp[iter->first].line_cost > line_tmp[cur].line_cost) {
DFS.push(iter->first);
line_tmp[iter->first].line_num = iter->second;
line_tmp[iter->first].from = cur;
line_tmp[iter->first].line_cost = line_tmp[cur].line_cost;
}
}
}
}
}
string mid_to = to;
string mid_from = line_tmp[mid_to].from;
int tmp_line_num = line_tmp[mid_to].line_num;
while(true){
// cout<<mid_from<<" "<<mid_to<<endl;
if(mid_from == "0") break;
if(line_tmp[mid_from].line_num == tmp_line_num) {
mid_from = line_tmp[mid_from].from;
}
else {
plan tmp_plan;
tmp_plan.from = mid_from;
tmp_plan.to = mid_to;
tmp_plan.line = tmp_line_num;
plan_way.push(tmp_plan);
tmp_line_num = line_tmp[mid_from].line_num;
mid_to = mid_from;
mid_from = line_tmp[mid_from].from;
}
}
int num_plan = plan_way.size();
for(int i = 0; i < num_plan; i++){
cout<<"Take Line#"<<plan_way.top().line<<" from "<<plan_way.top().from<<" to "<<plan_way.top().to<<"."<<endl;
plan_way.pop();
}
return ;
}
int main()
{
int n ;
cin>>n ;
way empty;
empty.from = "";
empty.line_num = -1;
empty.cost = INF;
empty.line_cost = 0;
//input map code
for(int i = 0 ; i < n ; i++){
int m ;
cin>>m ;
string front, behind, tmp;
//build the map of subway
for(int j = 0 ; j < m ; j++){
cin>>tmp ;
if(j == 0) front = tmp ;
else {
behind = tmp ;
if( subway_map.count(front) == 0 ){
subway_map[front] = new map<string, int> ;
line[front] = empty;
}
if( subway_map.count(behind) == 0 ){
subway_map[behind] = new map<string, int> ;
line[behind] = empty;
}
(*subway_map[front])[behind] = i+1 ;
(*subway_map[behind])[front] = i+1 ;
front = behind ;
}
}
}
//output map code for debug
// for(map<string, map<string, int> *>::iterator iter1 = subway_map.begin(); iter1 != subway_map.end(); iter1++){
// cout<<"From "<<iter1->first<<" to ";
// for(map<string, int>::iterator iter2 = iter1->second->begin(); iter2 != iter1->second->end(); iter2++){
// cout<<iter2->first<<" (Line#"<<iter2->second<<") ";
// }
// cout<<endl ;
// }
int k ;
cin>>k ;
for(int i = 0 ; i < k ; i ++){
cin>>from_station[i]>>to_station[i];
}
for(int i = 0 ; i < k ; i ++){
int depth = BFS(from_station[i], to_station[i]);
cout<<depth<<endl;
DFS(from_station[i], to_station[i], depth);
}
for(map<string, map<string, int> *>::iterator iter = subway_map.begin(); iter != subway_map.end(); iter++){
delete iter->second ;
}
return 0;
}
/*
input
4
7 1001 3212 1003 1204 1005 1306 7797
9 9988 2333 1204 2006 2005 2004 2003 2302 2001
13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011
4 6666 8432 4011 1306
3
3011 3013
6666 2001
2004 3001
2
5 1111 2222 4444 5555 6666
3 2222 3333 5555
1
1111 6666
*/
