← 返回题目列表

AtCoder · joi2020ho_d

D. 奥运巴士

中文机器翻译题面 查看原题

配点: 100 点

在JOI国家 有 N 个城市, 它们的编号最大为1 减去 N 。它还在一个方向上连接城市。 M 有几条巴士路线。 它们的编号最大为1 减去 M 。巴士路线 i (1 \leqq i \leqq M) 是一座城市 U_i 来自城市 这个想法是建立一条通往 V_i ,票价为 C_i 这是日元。巴士路线 i (1 \leqq i \leqq M) 然后,城市 U_i 城外骑行 除了 V_i 之外,您不能在任何地方下车。从一个城市到另一个城市可能有多条巴士路线运营。

奥运会即将在JOI国家举行。 JOI 是该国的交通部长。 K 董事长将 1 我们决定选择一条巴士路线,并在奥运期间反转该巴士路线的运营方向,但票价不变。换句话说,巴士路线 i (1 \leqq i \leqq M),奥运期间公交线路将在市内运行。 U_i 来自城市 这个想法是建立一条通往 V_i 现在将朝着 V_i 来自城市 这个想法是建立一条通往 U_i 运行。不过,巴士路线 反转 i 的行进方向 D_i 这将花费日元,这将由 K 主席的零用钱支付。此外,为了避免混乱,奥运期间公交车路线不能颠倒。

交通运输部部长 K 主席将 我计划在 1 和城市 它连接 N 之间换乘,然后乘坐巴士返回。我们希望通过仔细选择要反转运行方向的巴士路线,将往返总费用和反转运行方向的成本之和最小化。

鉴于城市数量和公交路线信息,该城市可以 编写一个程序,求 1 和城市 它连接 N 之间的往返总票价与反转行驶方向的成本之和的最小和。不过,无论您选择哪条巴士路线, 如果您无法在 1 和城市 它连接 N 之间来回,请改为 输出 −1 。


入力

输入是按以下格式从标准输入给出的。所有输入值都是整数。

N M
U_1 V_1 C_1 D_1
\vdots
U_M V_M C_M D_M

出力

都市 1 和城市 它连接 N 往返总票价之和的最小值 1 行。不过,无论您选择哪条巴士路线, 1 和城市 它连接 N 之间来回,请改为 输出 −1 。


制約

  • 2 \leqq N \leqq 200.
  • 1 \leqq M \leqq 50\,000.
  • 1 \leqq U_i \leqq N (1 \leqq i \leqq M).
  • 1 \leqq V_i \leqq N (1 \leqq i \leqq M).
  • U_i \neq V_i (1 \leqq i \leqq M).
  • 0 \leqq C_i \leqq 1\,000\,000 (1 \leqq i \leqq M).
  • 0 \leqq D_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq M).

小課題

  1. (5 点) M \leqq 1\,000.
  2. (11 点) M 是偶数,U_{2i − 1} = U_{2i},V_{2i − 1} = V_{2i},C_{2i − 1} = C_{2i} (1 \leqq i \leqq \frac{M}{2}).
  3. (21 点) C_i = 0 (1 \leqq i \leqq M).
  4. (63 点)没有额外的限制。

入力例 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 的行进方向是 当与 1 倒置时,城市 前往 1 来自城市 这个想法是建立一条通往 4 的最低票价为 6,都市 4 来自城市 这个想法是建立一条通往 1 的最低票价为 3 和城市 1 和城市 它连接 4 之间的总往返票价与反转行驶方向的费用之和为 10 变为。

都市 1 和城市 它连接 4 之间的总往返票价与反转运行方向的成本之和为 它不能小于 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 满足约束。


入力例 3

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

出力例 3

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

出力例 4

12

无需反转公交线路运行方向。


入力例 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

在此输入示例中,城市 前往 4 来自城市 这个想法是建立一条通往 3 的巴士路线 2 这本书存在。