该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

[AdditionalFile3471.zip](file://AdditionalFile3471.zip?type=additional_file)

P7407 [JOI 2021 Final] 机器人 / Robot

题目描述

给定一个 $N$ 点无向图，这 $N$ 个点编号为 $1 \sim N$，由 $M$ 条边连接，这 $M$ 条边编号为 $1 \sim M$，分别连接点 $A_i$ 与点 $B_i$。这 $M$ 条边染上了颜色，第 $i$ 条边的颜色为 $C_i$，保证 $C_i \in [1,M]$ 但不保证 $C_i$ 互不相等。

你很智能，如果我说一种颜色 $L$，满足下面这些要求的话：

• 存在一条边的颜色为 $L$ 且一个端点为你现在在的点。
• 不存在大于等于两条边满足颜色为 $L$ 且一个端点为你现在在的点。

你就会移动到这条边走向对面的端点，否则你就会原地不动。

你现在在点 $1$ 处，我要你移动到点 $N$ 处，我可以告诉你一些颜色你按照这些颜色走。但这个图有可能不满足能从 $1$ 走向 $N$ 这个条件，因此我要改变一些边的颜色。改变第 $i$ 条边的颜色使其变为另一个在区间 $[1,M]$ 里的数需要的代价为 $P_i$，我想问，至少需要多少代价才能让你成功移动到点 $N$？

输入格式

第一行两个整数 $N,M$ 代表无向图点数和边数。

接下来 $M$ 行每行四个整数 $A_i,B_i,C_i,P_i$ 描述一条边。

输出格式

一行一个整数代表最小代价，如果无法到达输出 $-1$。

输入输出样例 #1

输入 #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

输入输出样例 #2

输入 #2

5 2
1 4 1 2
3 5 1 4

输出 #2

-1

输入输出样例 #3

输入 #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

说明/提示

样例 1 解释

我可以进行如下操作：

• 将第 $4$ 条边的颜色改为 $4$，代价 $1$。
• 将第 $6$ 条边的颜色改为 $2$，代价 $2$。

总代价 $3$，然后我如下使唤你：

• 我说“颜色 $2$！”你从点 $1$ 移动到点 $2$。
• 我说“颜色 $4$！”你从点 $2$ 移动到点 $4$。

样例 2 解释

很遗憾，即使如此智能的你也到达不了第 $N$ 个点。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（34 pts）：$N \le 1000$，$M \le 2000$。
• Subtask 2（24 pts）：$P_i=1$。
• Subtask 3（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$2 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le A_i<B_i \le N$，$1 \le C_i \le M$，$1 \le P_i \le 10^9$，保证图无重边。

说明

翻译自 The 20th Japanese Olympiad in Informatics Final Round D ロボット的英文翻译 Robot。

#3471. 「JOI 2021 Final」机器人

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

译自 JOI 2021 Final T4「ロボット / Robot」

在 IOI 镇有 $N$ 个路口，编号为 $1$ 到 $N$。有 $M$ 条路，编号为 $1$ 到 $M$。每条路都双向连接两个路口。第 $i\ (1\le i\le M)$ 条路连接路口 $A_i$ 和 $B_i$。没有两条不同的路连接同一对路口。每条路有一种颜色，这种颜色用 $1$ 到 $M$ 闭区间内的一个整数表示。目前，路 $i$ 的颜色为 $C_i$。可能有多于一条路的颜色相同。

JOI 有限责任公司开发了一款在 IOI 镇的路口间移动的机器人。你无论何时告诉这个机器人一种颜色，机器人就会找到是这种颜色的路（注：并且这条路的一端应该是机器人所在的路口），然后经过这条路到达相邻的路口。然而，如果有多于一条与机器人所在的路口相连的路是你所说的这种颜色的话，机器人不会决定它应该走哪条路，并且会停下。

目前这个机器人在路口 $1$。你的任务是通过告诉机器人颜色，使其移动到路口 $N$。然而，这个机器人不一定能移动到路口 $N$。你可能需要预先改变某些道路的颜色使得机器人可以移动到路口 $N$。将一条路 $i\ (1\le i\le M)$ 改变成任意一种 $1$ 到 $M$ 闭区间中的颜色需要花费 $P_i$ 日元。

给定路口和道路的信息，写一个程序计算最小总花费。如果通过改变道路颜色也不能使得机器人移动到路口 $N$，则输出 $-1$。

输入格式

第一行两个整数 $N,M$；

接下来 $M$ 行，每行四个整数 $A_i,B_i,C_i,P_i$，表示第 $i$ 条路连接的两个路口 $A_i$ 和 $B_i$，当前颜色为 $C_i$，改变颜色的花费为 $P_i$。

输出格式

输出一行一个整数，表示最小总花费。如果通过改变道路颜色也不能使得机器人移动到路口 $N$，则输出 $-1$。

样例 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

输出

3

你可以花费 $1$ 日元，将道路 $4$ 的颜色从 $3$ 变为 $4$，再花费 $2$ 日元，将道路 $6$ 的颜色从 $4$ 变为 $2$。总花费为 $3$ 日元。

在此之后，告诉机器人走颜色 $2$ 的路，它将从路口 $1$ 移向路口 $2$。然后告诉机器人走颜色 $4$ 的路，机器人就会移向路口 $4$。

如果花费小于 $3$ 日元，则不可能让机器人移动到路口 $4$，所以输出 $3$。

样例 2

输入

5 2
1 4 1 2
3 5 1 4

输出

-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

输出

1

这个样例输入满足子任务 $2$ 的限制。

数据范围与提示

对于所有数据，满足：

• $2\le N\le 10^5$；
• $1\le M\le 2\times 10^5$；
• $1\le A_i<B_i\le N\ (1\le i\le N)$；
• $(A_i,B_i)\neq (A_j,B_j)\ (1\le i<j\le M)$；
• $1\le C_i\le M\ (1\le i\le M)$；
• $1\le P_i\le 10^9\ (1\le i\le M)$。

详细子任务附加限制及分值如下：