You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

最短来回

题目描述

给定一个 $N$ 个顶点 $M$ 条边的有向图，每条边从 $U_i$ 指向 $V_i$，经过这条边的代价为 $C_i$。

我们可以翻转一条边，即让他从 $U_i$ 指向 $V_i$ 变为从 $V_i$ 指向 $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$ 的边有两条。

数据规模与约定

对于 $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$。

• 子任务 1（5 分）：$M \le 1000$。

• 子任务 2（11 分）：$M$ 为偶数，且 $U_{2i}=U_{2i-1}$，$V_{2i}=V_{2i-1}$，$C_{2i}=C_{2i-1}$。

• 子任务 3（21 分）：$C_i=0$。

• 子任务 4（63 分）：无特殊限制。