PAT 甲 1131 Subway Map (30 分)
题目大意：
给一张地图，无向，给出n个行线，起点终点，不同行线要通过中转站转车，问最少经过多少站到达，如果站数相等，再根据最少转车次数判断。
要求输出站数，和每次转车的行线,这条行线的起点终点。
输入：
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
Take Line#3 from 3011 to 3013.
10
Take Line#4 from 6666 to 1306.
Take Line#3 from 1306 to 2302.
Take Line#2 from 2302 to 2001.
6
Take Line#2 from 2004 to 1204.
Take Line#1 from 1204 to 1306.
Take Line#3 from 1306 to 3001.
样例图：
真是难到我了，寻思着我写的题也不少了啊，怎么一点思路没得，应该是没吃饭引起的。
这题我开始想着用点来做，但是每个点可能在多个行线上，那么在判断的时候这个点u和他所连接的点v，即使开了个二维数组，用来保存每个点所包含的行线，那么在过从u点到v点，也根本没有办法判断是不是换行线了，因为就算两点行线不同，也有可能是一个行线上的，就算两点行线有相同的，也有可能是不同行线转来的（4011-1306-7797）到此死机。
这题根本问题我就想错了，其实可以继续想，如果从点分配行线不行，那么从边呢？4011-1306这条边是1,1306-7797这条边是2，那么就解决了行线处理问题，那么我们就需要另一个二维数组来保存边，边序号就对应点，再查询两点边颜色的时候，对应点来找到边序号从而找到对应颜色。
因为找最小而且有环，所以加个vis[]数组，最后别忘记加04d，ok
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+7,INF = 0x3f3f3f3f;
int line[N][11],link[N][11];//行线颜色，每个点的邻接点。
int vis[N],num[N],zpath[N],path[N];//num[u]是u点连出边的总数
int n,mzc,mcs;
int getline(int u,int v){
for(int i=1;i <= num[u];i++){ //暴力找点，通过点找到行线颜色
if(link[u][i] == v) return line[u][i];
}
}
void dfs(int now,int preline,int cs,int zc,int ed){ //当前点，上个行线，坐站数，转车数，终点
path[cs] = now;
if(cs > mcs || (cs == mcs && zc > mzc) ) return; //剪枝
if(now == ed){
mcs = cs,mzc = zc;
for(int i=0;i <= cs;i++)
zpath[i] = path[i];
return;
}
for(int i=1;i <= num[now];i++){
int v = link[now][i];
if(!vis[v]){
vis[v] = 1;
int line = getline(now,v);
if(line == preline) dfs(v,line,cs+1,zc,ed);
else dfs(v,line,cs+1,zc+1,ed);
vis[v] = 0;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i <= n;i++){
int k,u;scanf("%d%d",&k,&u);
for(int j=2;j <= k;j++){
int v;scanf("%d",&v);
link[u][++num[u]] = v;
line[u][num[u]] = i;
link[v][++num[v]] = u;
line[v][num[v]] = i;
u = v;
}
}
int k;scanf("%d",&k);
for(int i=1;i <= k;i++){
memset(vis,0,sizeof vis);
int st,ed;scanf("%d%d",&st,&ed);
mcs = mzc = INF;
dfs(st,-1,0,-1,ed); //这里我们转车数要从-1开始，因为起点行线是-1，那么不管第二个点是什么，行线都要+1
printf("%d\n",mcs);
int line1 = getline(zpath[0],zpath[1]);
for(int i=2;i <= mcs;i++){
int line2 = getline(zpath[i-1],zpath[i]);
if(line2 != line1){
printf("Take Line#%d from %04d to %04d.\n",line1,st,zpath[i-1]);
line1 = line2;
st = zpath[i-1];
}
}
printf("Take Line#%d from %04d to %04d.\n",line1,st,ed);
}
return 0;
}