PAT甲级1131 Subway Map【dfs】【输出方案】

题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805347523346432

题意：

告诉你一个地铁线路图，站点都是用四位数来编号。

现在问你从某一起点到某一终点，经过站数最少的乘车方式是什么？要输出方案。

如果站数相同要输出换乘较少的。

思路：

首先肯定是搜索没有问题了。因为要输出方案，所以bfs不太方便存答案。很容易想到用dfs

比较麻烦的是输出方案的时候，线路相同的那些站都合并在同一个线路里了。那么我们就再维护一个乘车区间结构体。

如果当前走的边和当前答案最后一条边是同一个线路，就把答案中最后一个乘车区间的终点改为当前的点。

回溯的时候不仅要把vis数组恢复，还要把答案恢复成dfs之前的，所以用一个tmpans来记录一下本次dfs之前的答案。

  1 #include<cstdio>
  2 #include<cstdlib>
  3 #include<map>
  4 #include<set>
  5 #include<iostream>
  6 #include<cstring>
  7 #include<algorithm>
  8 #include<vector>
  9 #include<cmath> 
 10 #include<stack>
 11 #include<queue>
 12 
 13 #define inf 0x7fffffff
 14 using namespace std;
 15 typedef long long LL;
 16 typedef pair<string, string> pr;
 17 
 18 struct station{
 19     int to;
 20     int line;
 21     station(){
 22     }
 23     station(int _to, int _line){
 24         to = _to;
 25         line = _line;
 26     }
 27 };
 28 
 29 struct mapnode{
 30     vector<station>list;
 31 };
 32     
 33 struct segment{
 34     int st, ed;
 35     int line;
 36     segment(){}
 37     segment(int _st, int _ed, int _line)
 38     {
 39         st = _st;
 40         ed = _ed;
 41         line = _line;
 42     }
 43 };
 44 
 45 struct Ans{
 46     int len;
 47     vector<segment>anslist;
 48     
 49     bool operator < (const Ans b)const{
 50         if(len == b.len)
 51             return anslist.size() < b.anslist.size();
 52         return len < b.len;
 53     }
 54 };
 55 
 56 const int maxn = 1e5 + 5;
 57 mapnode sta[maxn];
 58 int n, k;
 59 
 60 Ans ans, nowans;
 61 bool vis[maxn];
 62 void dfs(int st, int ed)
 63 {
 64     if(st == ed){
 65         if(nowans < ans)ans = nowans;
 66         //return;
 67     }
 68     
 69     if(ans < nowans)return;
 70     
 71     for(int i = 0; i < sta[st].list.size(); i++){
 72         int to = sta[st].list[i].to;
 73         if(!vis[to]){
 74             Ans tmpans = nowans;
 75             nowans.len++;
 76             if(sta[st].list[i].line == nowans.anslist.back().line){
 77                 nowans.anslist.back().ed = to;
 78             }
 79             else{
 80                 nowans.anslist.push_back(segment(st, to,sta[st].list[i].line));
 81             }
 82             
 83             vis[to] = true;
 84             dfs(to, ed);
 85             vis[to] = false;
 86             nowans = tmpans;
 87         }
 88     }    
 89 }
 90 
 91 void init()
 92 {
 93     memset(vis, 0, sizeof(vis));
 94     nowans.anslist.clear();
 95     nowans.len = 0;
 96     nowans.anslist.push_back(segment(-1, -1, -1));
 97     ans.anslist.clear();
 98     ans.len = inf;
 99     
100 }
101 
102 int main()
103 {
104     scanf("%d", &n);
105     for(int i = 1; i <= n; i++){
106         int m;
107         scanf("%d", &m);
108         int prev;
109         scanf("%d", &prev);
110         for(int j = 1; j < m; j++){
111             int to;
112             scanf("%d", &to);
113             sta[prev].list.push_back(station(to, i));
114             sta[to].list.push_back(station(prev, i));
115             prev = to;
116         }
117     }
118     
119     scanf("%d", &k);
120     while(k--){
121         int st, ed;
122         scanf("%d%d", &st, &ed);
123         init();
124         dfs(st, ed);
125         printf("%d
", ans.len);
126         for(int i = 1; i < ans.anslist.size(); i++){
127             printf("Take Line#%d from %04d to %04d.
", ans.anslist[i].line, ans.anslist[i].st, ans.anslist[i].ed);
128         }
129     }
130     
131     
132     return 0;
133 }