← 返回题目列表

AtCoder · wupc2012_5

E. 前往会场的路

中文机器翻译题面 查看原题
 比赛终于到了前一天。为了当天的准备,先确认一下去会场的路线吧!我打算步行前往会场。从我居住的城市到会场所在的城市(早稻田),需要经过几个城市。城市之间通过道路连接,不经过道路不能从一个城市移动到另一个城市。

 我绝对想在比赛中获胜。因此,为了万全起见,我要讲究吉利。我相信能被4或7整除的数是吉利的数。如果以出发时间为0,到达会场的时间能被4或7整除,我会感到心情愉快。但如果到达时的时间既不能被4也不能被7整除,我会觉得会在比赛中失败。为了在比赛中获胜,即使稍微绕路,也希望能在能被4或7整除的时间到达会场而移动。

 去会场的移动方法是自由的。可以返回已经走过的道路,也可以回到已经经过的城市或我居住的城市。但是,不能在道路中途掉头,也不能在到达会场后再折返。

 那么,当按照这个条件移动时,来试着求出到达会场所需的最短时间吧!

問題文

 N连接城市的M条道路的信息。每条道路连接两个不同的城市,可以在指定时间内双向通行。道路信息以两个不同城市的编号 (0~N-1) 及时间给出。“我”所在的城市编号是0,会场所在的城市编号是N-1,然后将出发时间设为0。当用一种到达会场所在城市的时间能被4或7整除的方法移动时,输出该最短的到达时间的程序。注意,一旦到达会场,就不能再移动。此外,途中不能返回,也不能在城市或道路中途休息。
图1:输入例3中城市和道路的情况

入力

输入是按以下格式从标准输入给出的。
N M
f_{1} t_{1} c_{1}
...
f_{m} t_{m} c_{m}
  • 1 行表示城市的数量 N(2 ≦ N ≦ 1000)与道路数量 M(1 ≦ M ≦ min(10000, N*(N-1)/2)) 由半角空格分隔。 您可以假设
  • 2 行目~ M+1 每一行包含各条道路的信息,也就是道路连接的两个城市编号 f_{i} 和 按字典顺序比较 t_{i},以及移动所需时间 c_{i} 由半角空格分隔。 关于
  • 各 i 关于 0 ≦ f_{i} ≦ N-1 和 0 ≦ t_{i} ≦ N-1 ,  f_{i} ≠ t_{i} , 1 ≦ c_{i} ≦ 100000 很满意。
  • 连接两座城市的道路数量最多为 1 条。也可能存在城市没有任何道路连接的情况。

出力

当以满足条件的方式移动到会场时,其最短时间输出到标准输出 1 行输出。
另外,保证可以以满足条件的方式移动到会场。

部分点

在满分100分中,30分部分,保证除了上述条件,还能在500单位时间以内移动到会场。

入力例 1

2 1
0 1 4

出力例 1

4
  • 可以从起点城市0以时间4到达终点城市1。总时间4是4的倍数,因此满足条件。所以答案是4。

入力例 2

3 2
0 1 15
1 2 5

出力例 2

20
  • 你可以在15小时内从起始城市0到城镇1,从城市1到目标城镇2需要5小时。由于总时间20是4的倍数,它满足了条件。因此,答案是20。

入力例 3

4 3
0 1 1
1 2 1
2 3 1

出力例 3

7
  • 你可以在时间1内从起始城镇0到城镇1,从城市1到城镇2,从城镇2到目标城镇3在1小时内。如果你沿着从起点到目标的最短路线走,总共需要3次,但既不是4,也不是7的倍数。如果你在城镇1和城市2之间来回两次,总时间是7,是7的倍数,所以满足条件。因此,答案是7。