Markov Trains

Description

Business is not going well for the Dutch Railway Company NS. Due to technical problems, they are forced to cancel many train services without advance notice. This is, of course, extremely frustrating for students who travel from home to school by train.
The worst thing about the whole situation is the randomness of the cancellations. Nobody knows in advance whether a train service will be cancelled; a cancellation is not announced until the official departure time. Since there is usually more than one possible route from home to school,people are often left with an 'if I had known this in advance I would have taken the other route' sort of feeling.
Recently, the statistics department of the NS found a revolutionary solution to this problem.They noticed that some train services are cancelled more often than others. In order to help the passengers, they decided to publish this information. The new timetables will state not just the time of departure and arrival of each service, but also its probability of cancellation.
The travel-planner software from the NS, which normally finds the fastest route between stations,must be updated to find the route which gives the best chance of arriving in time. This helps passengers to avoid trains that are likely to cause problems, instead taking a slightly longer, but more reliable route to school.
Given the new timetables, a departure station and time, a destination station and a desired arrival time, find the route which gives the best chance of arriving at the destination in time.
A route in this case is simply an ordered list of stations visited by the passenger, starting with the departure station and ending with the destination. The passenger will stick to the route, each time taking the first possible train to the next station. If a train is cancelled, he will just wait for the next train to that station.
The chance of arriving in time is taken to be the probability that the passenger, when following the route as described above, arrives at the destination station before or at the desired arrival time.When calculating this probability, we assume that train services are cancelled independently of each other and according to the probabilities stated in the timetable.
Input

The first line of the input contains a single positive integer indicating the number of runs. For each run, the input is as follows:
A line with a single positive integer n, the number of trains in the timetable (n <= 100).
n lines describing the timetable. Each line describes one train, stating its departure station x, the time of departure tx, its destination station y (x != y), the time of arrival ty (tx < ty) and its probability of cancellation p.Stations are identified by capital letters in the range 'A' . . . 'L'. Times are in the format hh:mm with 00 <= hh < 24 and 00 <= mm < 60. The probability p is a decimal real number with 0.0 <= p < 1.0. Input elements are separated by spaces.
A line with a departure station a, earliest departure time ta, destination station b (a != b) and desired arrival time tb (ta < tb). Station identifiers and times are like those in the timetable.
Output

The output consists of two lines for each run. The first line of each run contains the best possible route for the passenger as a list of station identifiers separated by spaces. The second line contains the probability that the passenger, when following the given route, arrives on time.The probability must be formatted as a decimal real number with exactly one digit before the decimal point, and exactly 4 digits after. The usual rules for rounding apply: round up if the next digit would be >= 5, otherwise round down.
Notes
When changing trains at an intermediate station, the earliest possible departure time is one minute after the time of arrival.
All times are on the same day; the journey does not cross midnight.
It never happens that two or more trains depart from the same station at the same time to the same destination station.
The input is such that there is a unique route with maximum probability.
The passenger will stick to his route, always taking the first available train to the next station. If a train is cancelled he will wait for the next train to that station. He will never try to be smart by taking faster trains or different routes.
Sample Input

2
3
A 12:00 B 12:15 0.1
A 12:10 B 12:14 0.23
A 12:20 B 12:30 0.456
A 12:00 B 12:30
4
A 12:00 B 12:15 0.1
A 12:05 B 12:13 0.15
B 12:20 C 12:35 0.12
A 12:15 C 12:33 0.4
A 12:00 C 13:00
Sample Output

A B
0.9895
A B C
0.8668

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
n步转移markov链的java实现,求源代码或者差不多的程序
-
求MCMC法估计动力学参数及其概率分布的Matlab编码,可有偿
-
已知状态空间,转移速率矩阵Q,用matlab画一个连续时间的markov链,具体要求如图
-
学校机器学习的目录, 全部英文
-
记一道字节跳动的算法面试题
点击蓝色“五分钟学算法”关注我哟加个“星标”,天天中午 12:15,一起学算法作者 | 帅地来源公众号 | 苦逼的码农前几天有个朋友去面试字节跳动,面试官问了他一道链表相...
程序员真是太太太太太有趣了!!!
网络上虽然已经有了很多关于程序员的话题,但大部分人对这个群体还是很陌生。我们在谈论程序员的时候,究竟该聊些什么呢?各位程序员大佬们,请让我听到你们的声音!不管你是前端开发...
史上最详细的IDEA优雅整合Maven+SSM框架(详细思路+附带源码)
网上很多整合SSM博客文章并不能让初探ssm的同学思路完全的清晰,可以试着关掉整合教程,摇两下头骨,哈一大口气,就在万事具备的时候,开整,这个时候你可能思路全无 ~中招了咩~ ,还有一些同学依旧在使用eclipse或者Myeclipse开发,我想对这些朋友说IDEA 的编译速度很快,人生苦短,来不及解释了,直接上手idea吧。这篇文章每一步搭建过程都测试过了,应该不会有什么差错。本文章还有个比较优秀的特点,就是idea的使用,基本上关于idea的操作都算是比较详细的,所以不用太担心不会撸idea!最后,本文
吃人的那些 Java 名词:对象、引用、堆、栈
作为一个有着 8 年 Java 编程经验的 IT 老兵,说起来很惭愧,我被 Java 当中的四五个名词一直困扰着:**对象、引用、堆、栈、堆栈**(栈可同堆栈,因此是四个名词,也是五个名词)。每次我看到这几个名词,都隐隐约约觉得自己在被一只无形的大口慢慢地吞噬,只剩下满地的衣服碎屑(为什么不是骨头,因为骨头也好吃)。
LeetCode解题汇总目录
此篇为LeetCode刷题的汇总目录,方便大家查找,一起刷题,一起PK交流! 已解题目 考点 LeetCode 1. 两数之和(哈希) LeetCode 2. 两数相加(单链表反转) LeetCode 9. 回文数 LeetCode 11. 盛最多水的容器(双指针) LeetCode 15. 三数之和 LeetCode 17. 电话号码的字母组合(回溯...
我花了一夜用数据结构给女朋友写个H5走迷宫游戏
起因 又到深夜了,我按照以往在csdn和公众号写着数据结构!这占用了我大量的时间!我的超越妹妹严重缺乏陪伴而 怨气满满! 而女朋友时常埋怨,认为数据结构这么抽象难懂的东西没啥作用,常会问道:天天写这玩意,有啥作用。而我答道:能干事情多了,比如写个迷宫小游戏啥的! 当我码完字准备睡觉时:写不好别睡觉! 分析 如果用数据结构与算法造出东西来呢? ...
不识 Pandas,纵是老手也枉然?
作者 |周志鹏 责编 | 郭 芮 这段时间和一些做数据分析的同学闲聊,我发现数据分析技能入门阶段存在一个普遍性的问题,很多凭着兴趣入坑的同学,都能够很快熟悉Python基础语法,然后不约而同的一头扎进《利用Python进行数据分析》这本经典之中,硬着头皮啃完之后,好像自己什么都会了一点,然而实际操作起来既不知从何操起,又漏洞百出。 至于原因嘛,理解不够,实践不够是两条老牌的拦路...
接班马云的为何是张勇?
上海人、职业经理人、CFO 背景,集齐马云三大不喜欢的张勇怎么就成了阿里接班人? 作者|王琳 本文经授权转载自燃财经(ID:rancaijing) 9月10日,张勇转正了,他由阿里巴巴董事局候任主席正式成为阿里巴巴董事局主席,这也意味着阿里巴巴将正式开启“逍遥子时代”。 从2015年接任CEO开始,张勇已经将阿里巴巴股价拉升了超过200%。但和马云强大的个人光环比,张勇显得尤其...
14 个实用的数据库设计技巧
点击上方“后端技术精选”,选择“置顶公众号”技术文章第一时间送达!作者:echozhjuejin.im/post/5d5b4c6951882569eb570958原始单据...
我在快手认识了 4 位工程师,看到了快速发展的公司和员工如何彼此成就!
作者 | 胡巍巍 出品 | CSDN(ID:CSDNnews) 从西二旗地铁站B口出来,步行700多米可以看到一个工业建筑风格的院子。这个独立的院子和后厂村各大互联网公司的高楼林立有些不同。 院子里有7栋6层高的楼,几栋楼之间打通,可以从A栋自由穿行到F栋。这里就是快手总部。这个园区可以容纳6000多名员工,目前40%以上是研发人员。 这些研发人员维护着快手这款日活超过2亿的ap...
让程序员崩溃的瞬间(非程序员勿入)
今天给大家带来点快乐,程序员才能看懂。 来源:https://zhuanlan.zhihu.com/p/47066521 1. 公司实习生找 Bug 2.在调试时,将断点设置在错误的位置 3.当我有一个很棒的调试想法时 4.偶然间看到自己多年前写的代码 5.当我第一次启动我的单元测试时 ...
用Python分析2000款避孕套,得出这些有趣的结论
到现在为止,我们的淘宝教程已经写到了第四篇,前三篇分别是: 第一篇:Python模拟登录淘宝,详细讲解如何使用requests库登录淘宝pc端。 第二篇:淘宝自动登录2.0,新增Cookies序列化,教大家如何将cookies保存起来。 第三篇:Python爬取淘宝商品避孕套,教大家如何爬取淘宝pc端商品信息。 今天,我们来看看淘宝系列的第四篇 我们在上一篇的时候已经将淘宝数据爬取下来了,...
Spring高级技术梳理
Spring高级技术梳理 序言正文SpringDate部分Spring全家桶之SpringData——预科阶段Spring全家桶之SpringData——Spring 整合Hibernate与Hibernate JpaSpring全家桶之SpringData——Spring Data JPASpring全家桶之SpringData——SpringData RedisSpringBoot部分Sp...
如何在Windows中开启"上帝模式"
原文链接 : https://mp.weixin.qq.com/s?__biz=MzIwMjE1MjMyMw==&amp;mid=2650202982&amp;idx=1&amp;sn=2c6c609ce06db1cee81abf2ba797be1b&amp;chksm=8ee1438ab996ca9c2d0cd0f76426e92faa835beef20ae21b537c0867ec2773be...
Docker 零基础从入门到使用
诺!这只可爱的小鲸鱼就是docker了! Docker 是什么? Docker 是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的镜像中,然后发布到任何流行的 Linux 或 Windows 机器上( 摘自百度 )。 Docker 能干什么? 在讲 Docker 能干什么之前,我们不妨先看看没有 Docker 和有Docker分别是个什么样子的? 场景一 某公司需要开发...
再见 Docker,是时候拥抱下一代容器工具了
什么是 Linux 容器?Linux 容器是由 Linux 内核所提供的具有特定隔离功能的进程,Linux 容器技术能够让你对应用及其整个运行时环境(包括全部所需文件)一...
不足20行 python 代码,高效实现 k-means 均值聚类算法
关于 k-means 均值聚类算法的原理介绍、实现代码,网上有很多,但运行效率似乎都有点问题。今天稍微有点空闲,写了一个不足20行的 k-means 均值聚类算法,1万个样本平均耗时20毫秒(10次均值)。同样的数据样本,网上流行的算法平均耗时3000毫秒(10次均值)。差距竟然达百倍以上,令我深感意外,不由得再次向 numpy 献上膝盖!
分享靠写代码赚钱的一些门路
作者 mezod,译者 josephchang10如今,通过自己的代码去赚钱变得越来越简单,不过对很多人来说依然还是很难,因为他们不知道有哪些门路。今天给大家分享一个精彩...
北漂程序员,扬帆起航的地方
随着耳畔传来“你看这碗又大又圆、你看这面又长又宽......碗大宽无影、像儿时的回忆......”听着挺带劲,于是看了一下手机,原来是吴亦凡的作品《大碗宽面》,随着入耳的旋律,脑子也不由自主的想起 10 年前,在平西府吃 5 块钱一大碗牛肉板面的情景。 平西府最有名的就是这个牌坊啦。记得每当有同事问起住哪里?都会自豪的说住在王府里;隔三差五也会邀请朋友去府上坐坐。其实打内心里讲,平西府是一个...
技术人员要拿百万年薪,必须要经历这9个段位
很多人都问,技术人员如何成长,每个阶段又是怎样的,如何才能走出当前的迷茫,实现自我的突破。所以我结合我自己10多年的从业经验,总结了技术人员成长的9个段位,希望对大家的职...
多线程编程是后台开发人员的基本功
这里先给大家分享一个小故事:在我刚开始参加工作的那年,公司安排我开发一款即时通讯软件(IM,类似于 QQ 聊天软件),在这之前我心里也知道如果多线程操作一个整型值是要加锁...
win10电脑工具整理 - 常用工具!
如题,本文主要为博主对电脑上安装的一些软件,所做的整理,当做备份用吧。 一、分类 系统工具 办公软件 编程开发 数据库相关 图片视频工具 网络及下载工具 解压缩工具 影音娱乐工具 二、软件工具 1.系统工具 1.1. 磁盘管理 PartAssist:一款好用的磁盘分区管理工具。 1.2. 修复、引导 EasyBCD:一款常用的系统引导和修复工具。 1.3. 虚拟机管理工具 win10...
Java 网络爬虫,就是这么的简单
这是 Java 网络爬虫系列文章的第一篇,如果你还不知道 Java 网络爬虫系列文章,请参看 学 Java 网络爬虫,需要哪些基础知识。第一篇是关于 Java 网络爬虫入门内容,在该篇中我们以采集虎扑列表新闻的新闻标题和详情页为例,需要提取的内容如下图所示: 我们需要提取图中圈出来的文字及其对应的链接,在提取的过程中,我们会使用两种方式来提取,一种是 Jsoup 的方式,另一种是 httpcli...
动画:用动画给面试官解释 TCP 三次握手过程
作者 | 小鹿 来源 | 公众号:小鹿动画学编程 写在前边 TCP 三次握手过程对于面试是必考的一个,所以不但要掌握 TCP 整个握手的过程,其中有些小细节也更受到面试官的青睐。 对于这部分掌握以及 TCP 的四次挥手,小鹿将会以动画的形式呈现给每个人,这样将复杂的知识简单化,理解起来也容易了很多,尤其对于一个初学者来说。 学习导图 一、TCP 是什么? TCP(Transmissio...
为什么程序员在学习编程的时候什么都记不住?
在程序员的职业生涯中,记住所有你接触过的代码是一件不可能的事情!那么我们该如何解决这一问题?作者 |Dylan Mestyanek译者 | 弯月,责编 | 屠敏出品 |...
500行代码,教你用python写个微信飞机大战
这几天在重温微信小游戏的飞机大战,玩着玩着就在思考人生了,这飞机大战怎么就可以做的那么好,操作简单,简单上手。 帮助蹲厕族、YP族、饭圈女孩在无聊之余可以有一样东西让他们振作起来!让他们的左手 / 右手有节奏有韵律的朝着同一个方向来回移动起来! 这是史诗级的发明,是浓墨重彩的一笔,是…… 在一阵抽搐后,我结束了游戏,瞬时觉得一切都索然无味,正在我进入贤者模式时,突然想到,如果我可以让更多人已不同的方式体会到这种美轮美奂的感觉岂不美哉? 所以我打开电脑,创建了一个 `plan_game.py`……
2019诺贝尔经济学奖得主:贫穷的本质是什么?
2019年诺贝尔经济学奖,颁给了来自麻省理工学院的 阿巴希·巴纳吉(Abhijit Vinayak Banerjee)、艾丝特·杜芙若(Esther Duflo)夫妇和哈...
linux:最常见的linux命令(centOS 7.6)
最常见,最频繁使用的20个基础命令如下: 皮一下,这都是干货偶,大佬轻喷 一、linux关机命令: 1.shutdown命令安全地将系统关机(推荐)参数说明: [-r] 重启计算器。 [-h] 关机后关闭电源〔halt〕。 [-c] cancel current process取消目前正在执行的关机程序。 [-time] 设定关机〔shutdown〕前的时间。 shutdown -h now ...
只因写了一段爬虫,公司200多人被抓!
“一个程序员写了个爬虫程序,整个公司200多人被端了。” “不可能吧!” 刚从朋友听到这个消息的时候,我有点不太相信,做为一名程序员来讲,谁还没有写过几段爬虫呢?只因写爬虫程序就被端有点夸张了吧。 朋友说,消息很确认并且已经进入审判阶段了。 01.对消息进一步确认 朋友认识几个律师朋友,和他们有一些业务来往,得知他们想尝试把业务扩展到程序员这个群体。那段时间我刚好离职也有时间,在朋友...
别在学习框架了,那些让你起飞的计算机基础知识。
我之前里的文章,写的大部分都是与计算机基础知识相关的,这些基础知识,就像我们的内功,如果在未来想要走的更远,这些内功是必须要修炼的。框架千变万化,而这些通用的底层知识,却是几乎不变的,了解了这些知识,可以帮助我们更快着学习一门知识,更加懂得计算机的运行机制。当然,在面试中也经常会被问到,特别是对于应届生,对于春秋招,也可以看看我前阵子写过的文章历经两个月,我的秋招之路结束了!。也有读者经常问的计算...
MySQL数据库—SQL汇总
一、准备 下文整理常见SQL语句的用法,使用MySQL5.7测试,参考了尚硅谷MySQL教程及用例。用例sql: 链接: https://pan.baidu.com/s/1tb3-12MRNFjV8drFlN6wzg&amp;shfl=sharepset 密码: fc2h 为了方便查阅可从右侧目录快速索引 二、DQL(Data Query Language)数据查询语言 1、语句顺序 书写顺序...
java学习路线导航【教学视频+博客+书籍整理】
在博主认为,学习java的最佳学习方法莫过于视频+博客+书籍+总结,前三者博主将淋漓尽致地挥毫于这篇博客文章中,至于总结在于个人,博主将为各位保驾护航,各位赶紧冲鸭!!!上天是公平的,只要不辜负时间,时间自然不会辜负你。 Java基础教学视频 Java零基础教程视频(适合Java 0基础,Java初学入门)【推荐】 JavaSE进阶入门项目实战视频教程_动力节点【推荐】 毕向东Java基础视频教程...
动画:用动画给女朋友讲解 TCP 四次分手过程
作者 | 小鹿 来源 | 公众号:小鹿动画学编程 写在前边 大家好,我们又见面了,做为一个业余的动画师,上次的用动画的形式讲解 TCP 三次握手过程再各大平台收到了广大读者的喜爱,说文章有趣、有货、有内容,也受到了很多读者的关注。很多读者留言说什么时候用动画讲一讲 TCP 四次挥手的过程,为了应大家的要求,今天我们就生动有趣的用动画给大家分享 TCP 四次挥手(分手)过程。 动画:用动画给...
程序员必须掌握的核心算法有哪些?
由于我之前一直强调数据结构以及算法学习的重要性,所以就有一些读者经常问我,数据结构与算法应该要学习到哪个程度呢?,说实话,这个问题我不知道要怎么回答你,主要取决于你想学习到哪些程度,不过针对这个问题,我稍微总结一下我学过的算法知识点,以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的,并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构,当然,我也会整理一些看过...
SQL基本语法入门 看这里就够了
SQL执行顺序 第一步:执行FROM 第二步:WHERE条件过滤 第三步:GROUP BY 分组 第四步:执行SELECT 投影列 第五步:HAVING条件过滤 第六步:执行ORDER BY排序 一、创建、删除库 -- 创建新数据库 CREATE DATABASE 数据库名; -- 删除数据库 DROP DATABASE 数据库名; 二、增加 1、添加列名、设置主键、设...
python 程序员进阶之路:从新手到高手的100个模块
在知乎和CSDN的圈子里,经常看到、听到一些 python 初学者说,学完基础语法后,不知道该学什么,学了也不知道怎么用,一脸的茫然。近日,CSDN的公众号推送了一篇博客,题目叫做《迷思:Python 学到什么程度可以面试工作?》,真实反映了 python 程序员在成长过程中的一些困惑。
相关热词 c#panel增加滚动条 c#中生成的dll文件 c# 模板类 c# 截取txt文本内容 c# 内存 占用 c#时间格式化 不带- c#替换字符串中指定位置 c# rdlc 动态报表 c# 获取txt编码格式 c#事件主动调用