洛谷 1346_电车_spfa

2019-11-06 07:48:41

字体：大中小

来源：转载

供稿：网友

题目描述

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

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

思路

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

#include <stdio.h>#include <queue>#include <iostream>#define maxn 50001#define INF 2147483647using 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]);}

上一篇：第二周作业1

下一篇：Codeforces Round #309 (Div. 2)C

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注