在 IOI 王国,时间的计量单位是 Byou,一天被划为
IOI 王国有
JOI 组织是 IOI 王国的秘密组织之一,为了保密,他们的成员不希望遇到安全检查。因此,如果 JOI 组织的成员想要通过某条路
JOI 组织有
请你求出每个成员需要的最短时间。
输入格式
第一行四个整数
接下来
接下来
输出格式
样例一
input
4 5 20 6 0 1 3 19 0 2 2 8 1 2 4 15 1 3 5 14 2 3 1 18 0 3 5 0 3 7 0 3 9 2 0 6 3 1 10 1 2 15
output
3 8 14 2 5 7
explanation
这组数据满足
在时刻
- 经过道路
,在时刻 到达城市 。 - 经过道路
,在时刻 到达城市 。
在时刻
- 经过道路
,在时刻 到达城市 。 - 经过道路
,在时刻 到达城市 。 - 经过道路
,在时刻 到达城市 。
在时刻
- 在原地停留直至第二天。
- 经过道路
,在时刻 到达城市 。 - 经过道路
,在时刻 到达城市 。
样例二
input
6 10 100 9 5 3 4 29 1 0 6 26 0 4 2 7 0 5 18 18 2 0 79 82 3 4 35 46 1 2 15 57 2 4 3 6 4 1 21 83 3 2 47 53 0 2 63 0 4 70 0 4 98 0 5 25 0 5 19 0 4 96 0 5 2 0 3 62 0 3 83
output
42 32 4 93 99 6 102 60 39
explanation
这组数据满足所有子任务的限制。
样例三
见附件下载中的 ex_route3.in
和 ex_route3.ans
。
这组数据满足
数据范围与提示
对于所有数据,保证
对于所有数据,保证图联通,且不存在自环重边。
在下发文件中,提供了一份 sample.cpp
来提供快速输入输出模板,注意如果你选择使用这份模板,你不应当使用其他包括 scanf,printf,cin,cout
在内的输入输出方式。你可以在 main
函数开始时调用 Init()
来获取输入,并在计算出答案后,保存至 ans
数组并调用 Output()
以输出答案。
时间限制:
空间限制: