原题地址：http://poj.org/problem?id=1847
Tram：有轨电车
这题就是构造一个有向无权图，然后每一个点都会有一个开关，这个开关指向他的其中一个出度。当途经这个点的时候，如果要从开关指向的边离开，则没事，如果不从开关指向的边离开，那么就要下车把开关掰到要离开的那条边上去。注意，离开之后那个开关是不会“弹”回去的。这跟现实铁路中的道岔还挺像。
这里我们用邻接表+SPFA来实现。注意是没有边权的。然后加了个switched数组，switched[i]表示第i个点开关指向的边的编号。在松弛代码中，我们会用到这个玩意儿。SPFA算法的队列使用STL的队列（手打队列麻烦）
注意最后不连通的判断，因为图是没有负权的（因为你最低也就是0，不可能走一圈下来掰了-1次开关吧），所以不用判断点是否入队超N次。不连通说明肯定没有搜到终点，终点的d数组肯定也没有被更新，所以就 判断是否为INF（0x3f3f3f3f）就能判断是否连通。
代码：
//Accepted
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
queue<int>q;
struct Edge
{
int v,next;
}a[10010];
int n,m=0,src,dest,tmp,tmp2,link[1010],d[1010],switched[1010];
bool visit[1010];
void addedge(int s,int d)
{
m++;
a[m].v=d;
a[m].next=link[s];
link[s]=m;
}
void spfa()
{
q.push(src);
d[src]=0;
visit[src]=true;
while(!q.empty())
{
int x=q.front();
q.pop();
visit[x]=0;
for(int i=link[x];i!=0;i=a[i].next)
{
if(d[x]+(switched[x]==a[i].v?0:1)<d[a[i].v])
{
d[a[i].v]=d[x]+(switched[x]==a[i].v?0:1);
if(visit[a[i].v]==false)
{
visit[a[i].v]=true;
q.push(a[i].v);
}
}
}
}
}
int main()
{
memset(d,0x3f,sizeof(d));
scanf("%d%d%d",&n,&src,&dest);
for(int i=1;i<=n;i++)
{
scanf("%d",&tmp);
for(int j=1;j<=tmp;j++)
{
scanf("%d",&tmp2);
if(j==1)switched[i]=tmp2;
addedge(i,tmp2);
}
}
spfa();
if(d[dest]==0x3f3f3f3f)printf("-1
");
else
printf("%d
",d[dest]);
return 0;
}