文档章节

P1346 电车

机智的帝江
 机智的帝江
发布于 2016/10/30 09:59
字数 632
阅读 7
收藏 0

题目描述

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

为了行驶向目标地点,电车司机不得不经常下车来切换开关,于是,他们想请你写一个程序,计算一辆从路口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

 首先来吐槽下这个题的名字。。为什么让我想起了某电*(和谐)之*。然后这道题算很水了。。数据很小。。spfa跟dijkstra都可以秒过。。代码也很简单
#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
const int maxn = 10500;
int n,A,B,d[maxn],vis[maxn];
vector<int >g[maxn];
vector<int >v[maxn];

void spfa()
{
    queue<int>q;
    d[A]=0;
    vis[A]=1;
    q.push(A);
    while(!q.empty())
    {
        int u=q.front();
        vis[u]=0;
        q.pop() ;
        for(int i=0;i<g[u].size();i++)
        {
            int t=g[u][i];
            int c=v[u][i];
            if(d[t]>d[u]+c)
            {
                d[t]=d[u]+c;
                if(!vis[t]) 
                {
                    q.push(t);
                    vis[t]=1;
                }
            }
        }
    } 
}
int main(){
    scanf("%d%d%d",&n,&A,&B);
    for(int i=1;i<=n;i++)d[i]=1e9;
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        for(int j=1;j<=x;j++)
        {
            int y;
            scanf("%d",&y);
            if(y==i)continue;
            g[i].push_back(y);
            if(j==1)v[i].push_back(0);
            else v[i].push_back(1); 
        }
    }
    spfa();
    if(d[B]==1e9) printf("%d",-1);
    else
        printf("%d",d[B]);
    return 0;
}

本文转载自:http://blog.csdn.net/loi__dijiang/article/details/52789531

机智的帝江
粉丝 0
博文 89
码字总数 4734
作品 0
莱芜
程序员
私信 提问
《日瓦戈医生》的结尾(Doctor Zhivago)

晚上,我躺在床上看书,突然读到这样一段: "至今我还记得大卫·里恩的电影《日瓦戈医生》结尾。医生说日瓦戈的心脏已经脆若薄纸。有一天他在莫斯科,坐在巴士上,车过街角,看到一个年轻女人...

阮一峰
2006/05/15
0
0
2018-11-09-今日得到-《电车难题》

今天分享的主题来自得到的每天听本书系列之《电车难题》 关于作者 托马斯·卡斯卡特,毕业于哈佛大学哲学专业,此后进入芝加哥大学研究神学。他的履历丰富,职业多变,从大学教授到临终关怀,...

韬声依旧在路上
2018/11/10
0
0
面对电车难题,自动驾驶交了一张白卷

     大数据文摘出品   编译:jin、钱天培   一辆刹车失灵的有轨电车正在急速行驶,前面的铁轨上绑着一群人, 如果任由电车行驶, 那群人必将罹难。   这时你站在铁轨正上方的天桥上...

大数据文摘
2018/11/02
0
0
研究人员尝试让人们相信无人驾驶汽车

     无人驾驶汽车通过各种技术让乘客更舒适。图片来源:JEFF SWENSEN   日前,电视和网络观众观看了这样一则广告,美国篮球明星LeBron James乘坐无人驾驶汽车。起初,James怀疑地盯着...

中国机器人
2018/01/10
0
0
自动驾驶汽车伦理大讨论:到底谁有权决定他人的生死?

雷锋网按:在即将到来的 CES 2018 之后,雷锋网将在美国科技的大本营硅谷举办 GAIR 硅谷智能驾驶峰会。目前早鸟票依然开放预订中,早鸟票将于太平洋时间 2017 年 12 月 24 日 23 时 59 分结束...

大壮旅
2017/12/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

关于AsyncTask的onPostExcute方法是否会在Activity重建过程中调用的问题

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接:https://blog.csdn.net/XG1057415595/article/details/86774575 假设下面一种情况...

shzwork
今天
6
0
object 类中有哪些方法?

getClass(): 获取运行时类的对象 equals():判断其他对象是否与此对象相等 hashcode():返回该对象的哈希码值 toString():返回该对象的字符串表示 clone(): 创建并返此对象的一个副本 wait...

happywe
今天
6
0
Docker容器实战(七) - 容器中进程视野下的文件系统

前两文中,讲了Linux容器最基础的两种技术 Namespace 作用是“隔离”,它让应用进程只能看到该Namespace内的“世界” Cgroups 作用是“限制”,它给这个“世界”围上了一圈看不见的墙 这么一...

JavaEdge
今天
8
0
文件访问和共享的方法介绍

在上一篇文章中,你了解到文件有三个不同的权限集。拥有该文件的用户有一个集合,拥有该文件的组的成员有一个集合,然后最终一个集合适用于其他所有人。在长列表(ls -l)中这些权限使用符号...

老孟的Linux私房菜
今天
7
0
面试套路题目

作者:抱紧超越小姐姐 链接:https://www.nowcoder.com/discuss/309292?type=3 来源:牛客网 面试时候的潜台词 抱紧超越小姐姐 编辑于 2019-10-15 16:14:56APP内打开赞 3 | 收藏 4 | 回复24 ...

MtrS
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部