#P51264. 「JOI 2020 Final」奥运公交
「JOI 2020 Final」奥运公交
题目描述
译自 JOI 2020 Final T4「オリンピックバス / Olympic Bus」
JOI 王国共有 个城市,这些城市从 到 编号。共有 条公交线路连接这些城市,这些线路从 到 编号。第 条公交线是从城市 到城市 的,票价为 日元。如果乘客乘坐第 条公交线,他只能在城市 上车,在城市 下车。从一个城市到另一个城市可能有多条公交线。
不久,JOI 王国将举办奥运会。K 理事长是 JOI 王国交通部部长。他会在奥运会之前选择最多一条公交线,并翻转这条公交线的起点和终点,但不改变票价。换句话说,如果他选择第 条公交线,在奥运会期间它将不会从 城市开往 城市,而是从 城市开往 城市,但票价仍为 日元。翻转一条公交线需要 日元,并且这个钱是 K 理事长出的。为了避免迷惑行为,在奥运会期间不允许翻转公交线。
因为 K 理事长是 JOI 王国的交通部部长,在奥运会期间他会使用这些公交线在城市 和城市 之间往返。通过恰当地选择翻转某条(或不翻转任何)公交线,他想要最小化往返城市 和城市 的公交总票价与翻转公交线的代价和。
现给定城市数和公交线情况,写一个程序求出这个最小代价和。如果不能通过翻转某条公交线来达到往返城市 与城市 的目的,请输出 。
输入格式
第一行两个整数 ,意义如题目描述;
接下来 行,每行四个整数 ,意义如题目描述。
输出格式
输出一行一个整数,如果可以通过翻转某条(或不翻转任何)公交线使得可以往返于城市 与城市 ,输出往返所需公交总票价与翻转公交线的代价和的最小值,否则输出 。
样例 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 理事长将翻转第二条公交线,这将花费 日元,那么从城市 到城市 的最小花费为 日元,从城市 到城市 的最小花费为 日元,加上翻转的代价 日元,总代价为 日元。
因为没有更优的答案了,所以输出 。
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
这个样例满足子任务 的限制。
4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1
2
这个样例满足子任务 的限制。
4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5
12
不是一定要翻转某条公交线。
4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5
-1
在这个样例中,从城市 到城市 的公交线有两条。
数据范围与提示
对于全部数据,。
详细子任务附加限制与分值如下表:
Subtask | 附加限制 | 分值 |
---|---|---|
是一个偶数, | ||
无附加限制 |