P1346 电车

Posted Tue Dec 10 2019. 695 words. 3 min read.

This article was last updated on days ago, the information described in the article may be outdated.

题目

[1]

题目描述

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

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

输入格式

第一行有 3 个整数 2<=N<=100,1<=A,B<=N,分别表示路口的数量,和电车的起点,终点。

接下来有 N 行,每行的开头有一个数字 Ki(0<=Ki<=N-1),表示这个路口与 Ki 条轨道相连,接下来有 Ki 个数字表示每条轨道所通向的路口,开关默认指向第一个数字表示的轨道。

输出格式

输出文件只有一个数字,表示从 A 到 B 所需的最少的切换开关次数,若无法从 A 前往 B,输出 -1。

输入输出样例

输入 #1

3 2 1
2 2 3
2 3 1
2 1 2

输出 #1

0

代码

其实非常简单啦,只需将开关默认指向的轨道的边权赋值为 0,其他为 1。

然后跑一边 spfa 就好了。

spfa 没死!!!

#include <iostream>
#include <cstdio>
#include <queue>
#define MAXN 10010
#define MAXM 500010
#define INF 2147483647
using namespace std;

queue<int> q;
struct Edge {
int next,to,w;
}edge[MAXM];
int n,m,s,ki,cnt,A,B;
int head[MAXN],vis[MAXN],dis[MAXN];

int spfa() {
for(int i=1;i<=n;i++)
dis[i] = INF;
q.push(A);
dis[A] = 0;
vis[A] = 1;
while(!q.empty()) {
int u = q.front();
q.pop();
vis[u] = 0;
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to;
if(dis[v]>dis[u]+edge[i].w) {
dis[v] = dis[u] + edge[i].w;
if(!vis[v]) {
vis[v] = 1;
q.push(v);
}
}
}
}
return dis[B]==INF ? -1 : dis[B];
}

void edge_add(int u,int v,int w) {
cnt++;
edge[cnt].next = head[u];
edge[cnt].to = v;
edge[cnt].w = w;
head[u] = cnt;
}

int main() {
cin >> n >> A >> B;
for(int i=1;i<=n;i++) {
cin >> ki;
for(int j=1;j<=ki;j++) {
cin >> m;
if(j==1)
edge_add(i,m,0);
else
edge_add(i,m,1);
}
}
cout << spfa();
return 0;
}

黄题++



Comments

Unable to load Disqus, please make sure your network can access.