HBC16036你的城市题解

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

2018年第一季度，美团旅行的酒店业务以5770万的订单总量，成为行业第一名，与此同时，美团旅行也提供机票、火车票、船票等各种服务，不断开辟新的目的旅游城市，最近新开的目的地，就包括对小A有特殊意义的偏僻小城C，“我来到 你的城市 熟悉的那一条街，”小A哼着歌，从北京出发，要去C城，这对他非常重要，必须当天到达，虽然交通并不是非常方便，问小A到达C城最少需要花费多少钱。

2018年第一季度，美团旅行的酒店业务以5770万的订单总量，成为行业第一名。 与此同时，美团旅行也提供机票、火车票、船票等各种服务，不断开辟新的目的旅游城市。最近新开的目的地，就包括对小A有特殊意义的偏僻小城C。 “我来到 你的城市 熟悉的那一条街。”小A哼着歌，从北京出发，要去C城。这对他非常重要，必须当天到达，虽然交通并不是非常方便。 但是，错过火车并不是一个小概率事件。为了保险起见，小A决定选择一个即使错过火车也存在补救措施的交通方案。（即假使未赶上原方案中的任何一班火车，依然可以改乘其他的车次能够在当天到达C城，但同时小A是一个乐观主义者，所以他认为改乘以后的所有车次都不会延误。）当然了，在满足上述条件的情况下，小A希望花费的钱越少越好（只考虑计划中的，不考虑发生意外时换乘带来的代价）。 城市及交通网可以看做一张n个点m条边的有向图。每个点代表一个城市（1号点代表北京，n号点代表C城）。每条边由一个五元组组成，表示存在一个车次，由ts时刻从城市x出发，在td时刻到达城市y，且花费为c元。 为了简化问题，ts，td均为以半小时为基本单位（具体格式见样例及Hint）。并假设每次中转最少需要花费半个小时，且中转只能发生在同一城市（即到达一个城市距离再次从这个城市出发至少需要间隔半个小时），注意，小 A 如果因为没赶上车次需要改乘，也需要半个小时的时间。 问小A到达C城最少需要花费多少钱（行程必须在这一天内完成，可以在0:00上车，也可以在24:00到达）。

想要在职场中立于不败之地？那就来试试全网最全C++题库，让您在练习中快速提升技能。

标签： HBC16036你的城市题解