AdditionalFile3255.zip

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

题目描述

给定一个含有 $N$ 个点，$M$ 条边的有向图，点的编号从 $1$ 到 $N$。每条边从 $U_i$ 指向 $V_i$，经过这条边的代价为 $C_i$。图中可能存在重边。

在最开始时，我们可以翻转至多一条边，即让这条边从 $U_i\to V_i$ 永久变为 $V_i\to U_i$，并产生 $D_i$ 的代价。

你要从点 $1$ 到点 $N$，再从点 $N$ 回到点 $1$，你想知道，通过翻转至多一条边，能得到的最小代价和为多少？

输入格式

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

接下来 $M$ 行每行四个整数 $U_i,V_i,C_i,D_i$ 代表一条边。

输出格式

一行一个整数代表最小代价和。无解输出 $-1$。

输入输出样例 #1

输入 #1

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

输出 #1

10

输入输出样例 #2

输入 #2

4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5

输出 #2

10

输入输出样例 #3

输入 #3

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1

输出 #3

2

输入输出样例 #4

输入 #4

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

输出 #4

12

输入输出样例 #5

输入 #5

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

输出 #5

-1

说明/提示

样例 1 解释

最优解为翻转第二条边，总代价为：

• 翻转的代价 $1$。
• 从点 $1$ 到点 $N$ 再返回的最短路径 $1 \to 2 \to 4 \to 3 \to 1$，代价为 $4+2+1+2=9$。

样例 4 解释

不一定需要翻转某条边。

样例 5 解释

从点 $4$ 到点 $3$ 的边有两条。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$M \le 1000$。
• Subtask 2（11 pts）：$M$ 为偶数，且 $U_{2i}=U_{2i-1}$，$V_{2i}=V_{2i-1}$，$C_{2i}=C_{2i-1}$。
• Subtask 3（21 pts）：$C_i=0$。
• Subtask 4（63 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $2 \le N \le 200$。
• $1 \le M \le 5 \times 10^4$。
• $1 \le U_i \le N$。
• $1 \le V_i \le N$。
• $U_i \ne V_i$。
• $0 \le C_i \le 10^6$。
• $0 \le D_i \le 10^9$。

说明

翻译自 第 19 回日本情報オリンピック　本選 D オリンピックバス。

#3255. 「JOI 2020 Final」奥运公交

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

译自 JOI 2020 Final T4「オリンピックバス / Olympic Bus」

JOI 王国共有 $N$ 个城市，这些城市从 $1$ 到 $N$ 编号。共有 $M$ 条公交线路连接这些城市，这些线路从 $1$ 到 $M$ 编号。第 $i\ (1\le i\le M)$ 条公交线是从城市 $U_i$ 到城市 $V_i$ 的，票价为 $C_i$ 日元。如果乘客乘坐第 $i$ 条公交线，他只能在城市 $U_i$ 上车，在城市 $V_i$ 下车。从一个城市到另一个城市可能有多条公交线。

不久，JOI 王国将举办奥运会。K 理事长是 JOI 王国交通部部长。他会在奥运会之前选择最多一条公交线，并翻转这条公交线的起点和终点，但不改变票价。换句话说，如果他选择第 $i$ 条公交线，在奥运会期间它将不会从 $U_i$ 城市开往 $V_i$ 城市，而是从 $V_i$ 城市开往 $U_i$ 城市，但票价仍为 $C_i$ 日元。翻转一条公交线需要 $D_i$ 日元，并且这个钱是 K 理事长出的。为了避免迷惑行为，在奥运会期间不允许翻转公交线。

因为 K 理事长是 JOI 王国的交通部部长，在奥运会期间他会使用这些公交线在城市 $1$ 和城市 $N$ 之间往返。通过恰当地选择翻转某条（或不翻转任何）公交线，他想要最小化往返城市 $1$ 和城市 $N$ 的公交总票价与翻转公交线的代价和。

现给定城市数和公交线情况，写一个程序求出这个最小代价和。如果不能通过翻转某条公交线来达到往返城市 $1$ 与城市 $N$ 的目的，请输出 $-1$。

输入格式

第一行两个整数 $N,M$，意义如题目描述；

接下来 $M$ 行，每行四个整数 $U_i,V_i,C_i,D_i$，意义如题目描述。

输出格式

输出一行一个整数，如果可以通过翻转某条（或不翻转任何）公交线使得可以往返于城市 $1$ 与城市 $N$，输出往返所需公交总票价与翻转公交线的代价和的最小值，否则输出 $-1$。

样例 1

输入

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

输出

10

假设 K 理事长将翻转第二条公交线，这将花费 $1$ 日元，那么从城市 $1$ 到城市 $4$ 的最小花费为 $6$ 日元，从城市 $4$ 到城市 $1$ 的最小花费为 $3$ 日元，加上翻转的代价 $1$ 日元，总代价为 $6+3+1=10$ 日元。

因为没有更优的答案了，所以输出 $10$。

样例 2

输入

4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5

输出

10

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

样例 3

输入

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1

输出

2

这个样例满足子任务 $3$ 的限制。

样例 4

输入

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

输出

12

不是一定要翻转某条公交线。

样例 5

输入

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

输出

-1

在这个样例中，从城市 $4$ 到城市 $3$ 的公交线有两条。

数据范围与提示

对于全部数据，$2\le N\le 200,1\le M\le 5\times 10^4,1\le U_i,V_i\le N,U_i\neq V_i,0\le C_i\le 10^6,0\le D_i\le 10^9$。

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

Subtask	附加限制	分值
$1$	$M\le 10^3$	$5$
$2$	$M$ 是一个偶数，$U_{2i-1}=U_{2i},V_{2i-1}=V_{2i},C_{2i-1}=C_{2i}\ (1\le i\le \frac{M}{2})$	$11$
$3$	$C_i=0\ (1\le i\le M)$	$21$
$4$	无附加限制	$63$