PAT甲級 1131 Subway Map (30分)

這道題有思維上比較簡單的解法，就是我寫的這種，這道題是無權圖最短路徑，用BFS求出并且儲存所有起點到終點的最短路徑，然後DFS一個一個判斷，這時候都是最短的了，隻用判斷第二标尺了，然後我的DFS寫的也和算法筆記一模一樣，是以算法筆記講的是Dijkstra+DFS，我這個是BFS+DFS，個人認為這種寫法是最适合跨考萌新的，因為别人的我都看不懂，這是我去看了看陳越資料結構想出來的。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000000;
const int maxn = 10010;
int n, m, k, c[110], s1, s2, d[maxn], mintrans;
vector<int> v[maxn], pre[maxn], path, ans;
map<int, int> mp;
void BFS(int s)
{	
	fill(d, d + maxn, INF);
	for(int i = 0; i < maxn; i++){
		pre[i].clear();
	}
	queue<int> q;
	q.push(s);
	d[s] = 0;
	while(!q.empty()){
		int now = q.front();
		q.pop();
		for(int i = 0; i < v[now].size(); i++){
			int t = v[now][i];
			if(d[t] == INF){
				d[t] = d[now] + 1;
				pre[t].push_back(now);
				q.push(t);
			}else if(d[t] == d[now] + 1) pre[t].push_back(now);
		}
	}
}
void DFS(int s, int v)
{
	if(s == v){
		path.push_back(v);
		int count = 0;
		for(int i = path.size() - 2; i > 0; i--){
			if(mp[path[i - 1] * 10000 + path[i]] != mp[path[i] * 10000 + path[i + 1]]) count++;
		}
		if(count < mintrans){
			mintrans = count;
			ans = path;
		}
		path.pop_back();
		return;
	}
	path.push_back(v);
	for(int i = 0; i < pre[v].size(); i++){
		DFS(s, pre[v][i]);
	}
	path.pop_back();
}
void showresult()
{
	int t = ans.size() - 1;
	printf("Take Line#%d from %04d to ", mp[ans[t] * 10000 + ans[t - 1]], ans[t]);
	for(int i = ans.size() - 2; i > 0; i--){
		if(mp[ans[i + 1] * 10000 + ans[i]] != mp[ans[i] * 10000 + ans[i - 1]]){
			printf("%04d.\nTake Line#%d from %04d to ", ans[i], mp[ans[i] * 10000 + ans[i - 1]], ans[i]);
		}
	}
	printf("%04d.\n", ans[0]);
}
int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &m);
		for(int j = 0; j < m; j++){
			scanf("%d", &c[j]);
			if(j){
				v[c[j]].push_back(c[j - 1]);
				v[c[j - 1]].push_back(c[j]);
				mp[c[j - 1] * 10000 + c[j]] = mp[c[j] * 10000 + c[j - 1]] = i;
			}
		}
	}
	scanf("%d", &k);
	while(k--){
		scanf("%d%d", &s1, &s2);
		mintrans = INF;
		BFS(s1);
		DFS(s1, s2);
		printf("%d\n", ans.size() - 1);
		showresult();
	}
	return 0;
}