撰写
When a driver has do drive from intersection A to the intersection B he/she tries to choose the route that will minimize the number of times he/she will have to change the switches manually.
Write a program that will calculate the minimal number of switch changes necessary to travel from intersection A to intersection B.
Input
Each of the following N lines contain a sequence of integers separated by a single blank character. First number in the i-th line, Ki (0 <= Ki <= N-1), represents the number of rails going out of the i-th intersection. Next Ki numbers represents the intersections directly connected to the i-th intersection.Switch in the i-th intersection is initially pointing in the direction of the first intersection listed.
Output
Sample Input
3 2 1 2 2 3 2 3 1 2 1 2
Sample Output
0
题意：有轨火车，可以改闸道以改变方向，每条线输入的第一个数字为既定路线，其余为改闸路线，问最少改多少次？
题解：将第一边设为0，其余为1，最短路一下。
#include<algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <vector>
#include <string>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define P(init,b,c) make_pair(init,make_pair(b,c))
#define rep(i,init,n) for (int i=init;i<=n;i++)
#define per(i,init,n) for (int i=n;i>=init;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef pair<int,pair<int,int> >pii;
typedef long long ll;
const ll mod = 1000000007;
ll gcd(ll init, ll b) { return b ? gcd(b, init%b) : init; }
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
int v;
int cost;
Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++)
dist[i]=INF;
vis[start]=true;
dist[start]=0;
queue<int>que;
while(!que.empty())
que.pop();
que.push(start);
memset(cnt,0,sizeof(cnt));
cnt[start]=1;
while(!que.empty())
{
int u=que.front();
que.pop();
vis[u]=false;
for(int i=0;i<E[u].size();i++)
{
int v=E[u][i].v;
if(dist[v]>dist[u]+E[u][i].cost)
{
dist[v]=dist[u]+E[u][i].cost;
if(!vis[v])
{
vis[v]=true;
que.push(v);
if(++cnt[v]>n) //cnt[i]为入队列次数，用来判定是否存在负环回路
return false;
}
}
}
}
return true;
}
int main()
{
int e,s,m,a,n;
while(scanf("%d%d%d",&n,&s,&e)!=EOF)
{
rep(i,1,n)E[i].clear();
for(int i=1;i<=n;i++)
{
scanf("%d",&m);
for(int j=1;j<=m;j++)
{
scanf("%d",&a);
if(j==1)
addedge(i,a,0);
else
addedge(i,a,1);
}
}
SPFA(s,n);
if(dist[e]==INF)
printf("-1\n");
else
printf("%d\n",dist[e]);
}
return 0;
}