[R60F]最短路 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一张 $n$ 个点 $m$ 条边的有向图（保证没有自环，但是可能有重边），第 $i$ 条边从 $u_i$ 指向 $v_i$，拥有三个属性 $w_i,r_i,b_i$，对于所有 $1 \le i \le m$，$w_i \ge \max(r_i,b_i)$。

你需要给图中的边染色，每条边要么染成红色要么染成蓝色。

染色后，对于一条从 $1$ 号点到 $n$ 号点的简单路径，定义该路径的权值为“路径中所有边的 $w_i$ 之和”$-$“路径中所有红色边的 $r_i$ 的最大值”$-$“路径中所有蓝色边的 $b_i$ 的最大值”。形式化地，设图中染成红色的边的下标组成的集合为 $R$，图中染成蓝色的边的下标组成的集合为 $B$，该路径经过的边的下标组成的集合为 $E$，则该路径的权值为

$$\sum_{i \in E} w_i-\max_{i \in (E \cap R)} r_i-\max_{i \in (E \cap B)} b_i$$

空集合最大值定义为 $0$。定义一种染色方案的权值为染色后所有从 $1$ 号点到 $n$ 号点的简单路径的权值最小值。

请你求出所有染色方案的权值的最小值。

保证至少存在一条从 $1$ 号点到 $n$ 号点的路径。

格式

输入格式

第一行两个整数 $n,m$，分别表示图中节点数量和边的数量。

接下来 $m$ 行，其中的第 $i$ 行包含五个整数 $u_i,v_i,w_i,r_i,b_i$，表示第 $i$ 条边及其三个属性。

输出格式

输出一行一个整数，表示所有染色方案的权值的最小值。

样例

样例输入 #1

4 5
1 2 5 1 1
2 4 5 1 1
1 3 100 99 1
3 4 100 1 99
1 4 15 7 7

样例输出 #1

2

样例输入 #2

5 7
1 2 6 6 1
2 3 6 1 6
3 2 1 1 1
3 5 10 10 1
1 4 25 1 20
4 5 25 20 1
2 5 30 15 15

样例输出 #2

6

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n,m \le$	$r_i,b_i \le$
$1$	$20$	$7$	$10$
$2$	$40$	$100$	$100$
$3$	$40$	$2 \times 10^5$	$10^{9}$

对于 $100\%$ 的数据：$2 \le n \le 2 \times 10^5$，$1 \le m \le 2 \times 10^5$，$1 \le u_i,v_i \le n$，$u_i \ne v_i$，$1 \le w_i \le 10^9$，$1 \le r_i,b_i \leq 10^{9}$，对于所有 $1 \le i \le m$，$w_i \ge \max(r_i,b_i)$。保证至少存在一条从 $1$ 号点到 $n$ 号点的路径。