PID266 / Dejected Birthday-允诺
题目描述

9.19是青子的生日...

而在那日晚,基德发出了盗窃"忧郁的生日"的预告函.

快斗在两难的抉择下,最终决定:以最快速度将"忧郁的生日"收入囊中,再赶去为青子表演魔术--这是他对青子的允诺.

"忧郁的生日"被保存在一个深不可测的大楼里.而从大门到最里面的房间有无数条路径.整个大楼可以被看做一个巨大的无向图,有些

房间之间有路,而有些没有.每条路要消耗基德不一样的时间.在最里面的房间内存放着"忧郁的生日".这块宝石被一层密码锁保护着.

打开这层密码锁也需要一段时间.假设基德盗窃时没有人来干扰(警卫都干什么吃的).给出基德开始盗窃的时间,整个大楼中连通的情

况以及打开这个密码锁的时间.求出快斗能对青子允诺到达生日会场的最早时间.若此时间晚于24:00则输出"Sad".

输入格式

输入文件共k+3行.

第一行,是基德开始盗窃的时间.格式为形如"xx:xx"的24小时制形式(如13:00);

第二行到第k+2行为大楼的连通情况.

第二行共2个整数n,k.n为房间总数,共k对房间之间有路径.进口为1号房间,"忧郁的生日"存放在n号房间里.

第三行到第k+2行,每行共3个整数a,b,c.表示a号和b号房间之间有路径,该路径费时为c分钟.

第k+3行为打开密码锁的时间,格式为"x min/second/hour"表示打开密码锁需要x分钟/秒/小时.

数据范围:

n<=500, k<=2000

输出格式

输出共一行,输出快斗能允诺青子的最早时间,格式如同输入中的开始盗窃时间格式"xx:xx",24小时制.若最早时间超过24:00则输出

"Sad".

数据保证一定能抵达中心房间。需要注意的是,输入数据中可能会出现0号结点。这些数据均需被忽略不计。而输入中开始时间必定

遵守"xx:xx"格式,如"05:00";但输出中你必须这样表示:"5:00"而不应出现一开始的“0”。

样例输入
样例输出
提交题目 Error [ 更改语言 ] Language
C C++ Pascal Python2
相关讨论
查看更多讨论
发布新讨论 讨论