洛谷 1346_电车_spfa

发布于 2019-05-16  7 次阅读


题目描述

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

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


思路

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


#include 
#include 
#include 
#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  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
]]>