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

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 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

样例输出 1

10

样例说明 1

假设 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

样例输出 2

10

样例说明 2

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

样例输入 3

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

样例输出 3

2

样例说明 3

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

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

样例说明 4

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

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

样例说明 5

在这个样例中,从城市 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