← 返回题目列表

AtCoder · joi2021ho_d

D. 机器人

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

配点: 100 点

位于 IOI 镇 有 N 交叉路口, 它们的编号最大为1 从 N 。另外,M 有一条书路, 它们的编号最大为1 从 M 。每条路径都是 它连接 2 两个方向的不同交叉路口。路 i (1 \leqq i \leqq M) 是一个交集 A_i 和交叉路口 B_i 已连接。2 书中的不同道路从未连接同一组交叉路口。在这些道路上 1 以上 M 道路涂有由以下整数表示的颜色。 i 的当前颜色是 C_i 。多条道路可以涂成相同的颜色。

JOI 开发了一种机器人,可以在 IOI 镇的十字路口移动。当你告诉这个机器人道路的颜色时,机器人就会沿着指定颜色的路径移动到相邻的路口。但与机器人当前所在路口相连的道路中,指定颜色的道路为 2 如果有多个,它将停止而无法确定下一条路径。

您的目标是 1 向十字路口的机器人发出几条指令。 就是将其移动到 N 。然而,这对于当前的道路颜色来说不一定可行,因此需要改变一些道路的颜色。提前通过重新喷漆, 交叉路口机器人 我希望能够将其移至 N 。路 i (1 \leqq i \leqq M) 是 P_i 乘以日元,1 以上 M 您可以将其重新绘制为下面您最喜欢的整数颜色。

给定有关十字路口和道路的信息,编写一个程序来查找所需的最低金额。然而,无论你如何改变道路的颜色,机器人都无法穿过路口。 如果您无法将其移至 N ,请改为 输出 -1 。


入力

输入是按以下格式从标准输入给出的。所有输入值都是整数。

N M
A_1 B_1 C_1 P_1
\vdots
A_M B_M C_M P_M

出力

标准输出所需的最小金额 输出为 1 行。然而,无论你如何改变道路的颜色,机器人都无法穿过路口。 N ,请改为 输出 -1 。


制約

  • 2 \leqq N \leqq 100\,000.
  • 1 \leqq M \leqq 200\,000.
  • 1 \leqq A_i < B_i \leqq N (1 \leqq i \leqq M).
  • (A_i, B_i) \neq (A_j, B_j) (1 \leqq i < j \leqq M).
  • 1 \leqq C_i \leqq M (1 \leqq i \leqq M).
  • 1 \leqq P_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq M).

小課題

  1. (34 点) N \leqq 1\,000,M \leqq 2\,000.
  2. (24 点) P_i = 1 (1 \leqq i \leqq M).
  3. (42 点)没有额外的限制。

入力例 1

4 6
1 4 4 4
3 4 1 3
1 3 4 4
2 4 3 1
2 3 3 2
1 2 4 2

出力例 1

3

1 米奇圆 4 颜色 颜色来自 3 重新绘制为 4 , 将其重新绘制为2 米奇圆 6 颜色 颜色来自 4 重新绘制为 2 。总计 3 花费日元。

结果,交集 给机器人上色 1 通过命令 2 ,机器人移动到交叉路口。 您可以将其移至 2 。接下来,给机器人上色。 您可以将其移至 4 ,机器人移动到交叉路口。 您可以将其移至 4 。

2 将机器人移动到圆圈下方的交叉点 由于无法移动到 4 , 输出3 。


入力例 2

5 2
1 4 1 2
3 5 1 4

出力例 2

-1

无论你如何重新粉刷道路,你都可以将机器人移动到十字路口。 它无法移动到 5 。因此,-1 。


入力例 3

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

出力例 3

1

此输入示例是一个小作业。 2 满足约束。 给出了


入力例 4

13 21
7 10 4 4
3 6 4 7
8 10 4 5
3 9 2 5
1 4 4 5
2 6 4 2
3 11 2 2
3 8 16 2
8 11 16 1
6 10 4 14
6 8 16 6
9 12 16 5
5 13 4 6
1 12 4 7
2 4 4 18
2 9 4 10
2 12 4 6
10 13 4 28
5 7 2 5
5 11 2 16
7 13 4 20

出力例 4

7