1131 Subway Map (30分)

这算比较难的一个题了，主要有几个细节需要注意：

①：关于某条线路中转站数量的计算：

不可以直接通过计算所经过的点是否为中转站，因为即使这个点是中转站，但是在某条线路上仍可能是不需要中转。

②：关于输出，切记要按4位输出，不然无法过测试点2

附本人代码：

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<string.h>
#include<algorithm>
using namespace std;
int line[10001][10001], s, d, maxsum, maxctr;
bool tran[10010], flag[10010];
map<int, vector<int>>Ma;
vector<int>tmp, ans;
void dfs(int pre,int now, int sum,int lin,int ctr) {
	tmp.push_back(now);
	if (pre != now) {
		if (lin != line[pre][now]) {//及其关键，统计改变线路 的点
			ctr++;		//注意不可以直接统计该点是否为中专点，因为即使这里可以中专，该路线可能在这个点处不中专。
			lin = line[pre][now];
		}
	}
	if (now == d) {
		if (sum < maxsum) {
			maxsum = sum;
			ans = tmp;
			maxctr = ctr;
		}
		else if (sum == maxsum && ctr < maxctr) {
			ans = tmp;
			maxctr = ctr;
		}
		tmp.pop_back();
		return;
	}
	flag[now] = true;
	for (int i = 0; i < Ma[now].size(); i++) {
		if (!flag[Ma[now][i]])dfs(now,Ma[now][i], sum + 1,lin,ctr);
	}
	flag[now] = false;
	tmp.pop_back();
}
int main() {
	int N, num, val, M;
	scanf("%d", &N);
	for (int i = 1; i <=N; i++) {
		scanf("%d", &num);
		int pre = -1;
		for (int j = 0; j < num; j++) {
			scanf("%d", &val);
			if (pre != -1) {
				line[val][pre] = line[pre][val] = i;//保存两个点之间的地铁线编号
				Ma[val].push_back(pre);//与他相连的点个数
				Ma[pre].push_back(val);//同上
			}
			pre = val;
		}
	}
	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d%d", &s, &d);
		maxsum = 9999;
		maxctr = 9999;
		dfs(s,s,0,0,0);
		printf("%d\n", ans.size() - 1);
		int head = ans[0], lin = line[ans[0]][ans[1]];
		for (int i = 1; i < ans.size(); i++) {
			if (line[ans[i - 1]][ans[i]] != lin) {
				printf("Take Line#%d from %04d to %04d.\n",lin,head,ans[i-1]);
				lin = line[ans[i - 1]][ans[i]];
				head = ans[i - 1];
			}
		}
		printf("Take Line#%d from %04d to %04d.\n", lin, head, ans.back());
	}
	return 0;
}