← 返回题目列表

AtCoder · code_thanks_festival_2015_g

G. 变色龙

中文机器翻译题面 查看原题

問題文

这是一个丛林,你的变色龙朋友住在那里。

在丛林中 有 N 方格,并且方格有 它们的编号最大为 1 到 N 。还有,在丛林里 M 有一条书路,路是 它们的编号最大为 1 到 M 。每一条路都是不同的 2 它连接两个方块并且可以双向移动。

你的朋友变色龙将在广场参加 2015 年 CODE THANKS FESTIVAL。 1 卡拉广场 我即将前往 N 。变色龙使用道路在广场之间移动,但丛林道路充满了未知的危险,所以它们不使用道路。 当使用 i (1 ≦ i ≦ M) 时,变色龙的身体颜色是 必须是 c_i 。还有,路 使用 i 移动时,时间为 需要 t_i 。

变色龙是正方形 从 1 开始移动时,身体颜色变为 1 。变色龙可以在任何方格内改变颜色; 颜色来自 x 卡拉色 y 改变机身颜色需要时间|x-y|只需要 .还有,变色龙就在广场上 当它到达 N 时,它会停止移动,但它的身体颜色可以是任何颜色。

你是变色龙方块 我们决定找到到达 N 所需时间的最小可能值。


入力

输入将以以下形式从标准输入给出。

N M
a_1 b_1 c_1 t_1
a_2 b_2 c_2 t_2
:
a_M b_M c_M t_M
  • 1 行中的方格数 N (2 ≦ N ≦ 40,000) 和道路数量 M (1 ≦ M ≦ 80,000) 用空格分隔。
  • 2 从行 M 行提供有关道路的信息。其中 行 i (1 ≦ i ≦ M) 在行 4 整数值 a_i, b_i (1 ≦ a_i < b_i ≦ N), c_i (1 ≦ c_i ≦ 1,000,000,000), t_i (1 ≦ t_i ≦ 1,000,000,000) 用空格分隔。这就是路 i 是正方形 a_i 和 b_i 这条路连接着 i 过河时,身体颜色发生变化。 c_i 和旅行时间 t_i 表示需要。
  • i ≠ j 然后,a_i ≠ a_j 或 b_i ≠ b_j 成立。
  • 広場 1 到任何其他方块。 1 保证您可以通过多条道路来回。

出力

变色龙广场 到达 N 所需的最短可能时间是 1 行输出。还在输出末尾添加换行符。


入力例1

6 7
1 2 1 6
1 3 7 4
2 3 3 4
2 5 6 6
3 4 4 6
3 5 1 3
5 6 2 4

出力例1

22

对于此示例输入,最好按如下方式移动:

  • 最初、広場 1 机身颜色为彩色 有一只 1 变色龙。 使用
  • 道 1 进行平方 转至 1 卡拉广场 我即将前往 2 。变色龙身体颜色是彩色的 1 因此可以移动,总共花费的时间是 6 。
  • 広場 2 改变车身颜色 将其更改为 1 卡拉色 3 。总共花费的时间是 6+2 = 8 。
  • 道 3 进行平方 转至 2 卡拉广场 我即将前往 3 。变色龙身体颜色是彩色的 3 因此可以移动,总共花费的时间是 8+4 = 12 。
  • 広場 3 改变车身颜色 将其更改为 3 卡拉色 1 。总共花费的时间是 12+2 = 14 。
  • 道 6 进行平方 转至 3 卡拉广场 我即将前往 5 。变色龙身体颜色是彩色的 1 因此可以移动,总共花费的时间是 14+3 = 17 。
  • 広場 6 改变车身颜色 将其更改为 1 卡拉色 2 。总共花费的时间是 17+1 = 18 。
  • 道 7 进行平方 转至 5 卡拉广场 我即将前往 6 。变色龙身体颜色是彩色的 2 因此可以移动,总共花费的时间是 18+4 = 22 。

入力例2

3 3
1 2 1 10
1 3 3 3
2 3 5 2

出力例2

5