题目描述

在一个神奇的小镇上有着一个特别的电车网络，它由一些路口和轨道组成，每个路口都连接着若干个轨道，每个轨道都通向一个路口（不排除有的观光轨道转一圈后返回路口的可能）。在每个路口，都有一个开关决定着出去的轨道，每个开关都有一个默认的状态，每辆电车行驶到路口之后，只能从开关所指向的轨道出去，如果电车司机想走另一个轨道，他就必须下车切换开关的状态。

为了行驶向目标地点，电车司机不得不经常下车来切换开关，于是，他们想请你写一个程序，计算一辆从路口A到路口B最少需要下车切换几次开关。

思路

将第一个点边权设为0其余为1，跑一边spfa就可以了
注意-1！！！！！！！！

#include <stdio.h>
#include <queue>
#include <iostream>
#define maxn 50001
#define INF 2147483647
using namespace std;
int l=0,s;
struct arr 
{ 
    int x,y,w,next;   
};
int x,y,z;
arr edge[maxn];
int ls[maxn];
int state[maxn];
bool exits[maxn];
int spfa()
{
    int i;
    queue <int> t;
    t.push(s);
    state[s]=0;
    exits[s]=true;
    do
    {
        int tt=t.front();
        t.pop();
        i=ls[tt];
        while (i!=0) 
        {
            if (state[edge[i].x]+edge[i].w<state[edge[i].y])
            {
                state[edge[i].y]=state[edge[i].x]+edge[i].w;
                if (exits[edge[i].y]==false)
                {
                    t.push(edge[i].y);
                    exits[edge[i].y]=true;
                }
            }
            i=edge[i].next;
        }
        exits[tt]=false;
    }
    while (!t.empty());
}
int main()
{
    int j,k,n,m,e;
    scanf("%d%d%d",&n,&s,&e);
    for (int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        for (int j=1;j<=x;j++)
        {
            int y;
            scanf("%d",&y);
            l++;
            edge[l].x=i; edge[l].y=y; edge[l].next=ls[edge[l].x];
            ls[i]=l;
            if (j==1) edge[l].w=0;
            else edge[l].w=1;
        }
    }
    for (int i=1;i<maxn;i++)
        state[i]=INF;

    spfa();
    if (state[e]==INF) state[e]=-1;
    printf("%d\n",state[e]);
}