← 返回题目列表

AtCoder · joi2024_yo2_e

E. 高速公路通行费

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

配点: 100 点

問題文

JOI王国是 N 是一个由城市组成的王国,这些城市有 它们的编号最大为 1 我决定将所有值添加到 N 。 JOI Kingdom拥有连接这些城市的网络。一方通行高速公路 M 书籍可用, 它们的编号最大为1 我决定将所有值添加到 M 。 高速公路 i (1 \leqq i \leqq M) 穿过城市 你可以移动到 A_i 来自城市 它的编号最大为 B_i ,经过的时间是 L_i 。

每次使用各高速公路时都会收取通行费。 高速公路 i 通行费最便宜。 C_i 然而,JOI王国的所有工人都不喜欢加班,所以有一定的标准时间 您距离 0 越远,收费就越高。 具体来说,城市 A_i 到时间 t 离开高速公路 经过 i 时,过路费不变 K 表示为 C_i + K\times |t| 。 然而,|t| 是 它仅由 t 的绝对值。

都市 1 您住在您朋友居住的城市。 N 。 你开车穿过高速公路到城市 我想去 1 来自城市 它的编号最大为 N ,所以首先我想看看是否可以,如果可以的话,我还想知道最低的总过路费是多少。 但您可以自由决定旅行路线以及从每个城市出发的时间。 尤其是城市 您可能会在负时间离开 1 ,或者您可能会在城市停留一段时间而不使用高速公路。

高速公路信息和常量 K 判断是否可以移动到 1 来自城市 它的编号最大为 N , 如果可能的话,编写一个程序来计算通行费的最小总和。

在这个问题的约束下,可以 如果可以行驶到 1 来自城市 它的编号最大为 N ,则可以证明路费的最小总和始终是整数。

制約

  • 2 \leqq N \leqq 4\,000.
  • 1 \leqq M \leqq 8\,000.
  • 0 \leqq K \leqq 100\,000.
  • 1 \leqq A_i \leqq N (1 \leqq i \leqq M).
  • 1 \leqq B_i \leqq N (1 \leqq i \leqq M).
  • A_i \neq B_i (1 \leqq i \leqq M).
  • 1 \leqq L_i \leqq 1\,000\,000 (1 \leqq i \leqq M).
  • 0 \leqq C_i \leqq 10^9 (1 \leqq i \leqq M).
  • 所有输入值都是整数。

小課題

  1. (9 点) N \leqq 100,M \leqq 200,K = 0.
  2. (21 点) N \leqq 100,M \leqq 200,L_i \leqq 20 (1 \leqq i \leqq M).
  3. (13 点) N \leqq 100,M = N - 1,A_i = i,B_i = i+1 (1 \leqq i \leqq M).
  4. (23 点) N \leqq 100,M \leqq 200 并满足以下约束。
    • N 是偶数,\lfloor \frac{B_i}{2} \rfloor - \lfloor \frac{A_i}{2} \rfloor = 1 (1 \leqq i \leqq M). 在这里,\lfloor x \rfloor 是 它仅由 x 代表以下最大的整数。
  5. (16 点) N \leqq 100,M \leqq 200.
  6. (11 点) N \leqq 1\,500,M \leqq 3\,000.
  7. (7 点)没有额外的限制。

入力

输入按以下格式给出。

N M K
A_1 B_1 L_1 C_1
A_2 B_2 L_2 C_2
\vdots
A_M B_M L_M C_M

出力

市内直通高速公路 如果无法移动到 1 来自城市 它的编号最大为 N , 输出-1 。 如果可能,表示最小总通行费的整数。 1 行。


入力例 1

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

出力例 1

15

以下是JOI王国的城市和道路图。 圆圈代表城市,箭头代表道路,每条道路旁边都有该道路的名称。 L_i 和 C_i 的值按​​此顺序写入。 圆圈内写的数字代表该城市的编号。

如果您按以下方式移动,则总通行费将为 它变成 15 。

  • 時刻 -1 : 都市 1 出发 前往 3 。通行费 10+2\times \left|-1\right|=12 需要。
  • 時刻 0 : 都市 3 立即前往市区 4 。通行费 3+2\times |0|=3 需要。
  • 時刻 5 : 都市 4 。

总通行费为 15 由于没有移动方法使其变小,15 。

此输入示例是一个小作业。 2,5,6,7 满足约束。


入力例 2

4 4 0
1 2 3 2
1 3 1 10
2 3 1 4
3 4 5 3

出力例 2

9

入力例 1 是什么? 仅 K 的值不同。 到达

如果您按以下方式移动,则总通行费将为 它变成 9 。

  • 時刻 -3 : 都市 1 出发 前往 2 。通行费 2+0\times \left|-3\right|=2 需要。
  • 時刻 0 : 都市 2 立即前往市区 3 。通行费 4+0\times |0|=4 需要。
  • 時刻 1 : 都市 3 并继续前往市区。 留在 3 。 由于无法移动到
  • 時刻 3 : 都市 3 出发 前往 4 。通行费 3+0\times |3|=3 需要。
  • 時刻 8 : 都市 4 。

总通行费为 9 由于没有移动方法使其变小,9 。

此输入示例是一个小作业。 1,2,5,6,7 满足约束。


入力例 3

2 1 10
2 1 4 7

出力例 3

-1

市内直通高速公路 如果无法移动到 1 来自城市 它的编号最大为 2 ,-1 。

此输入示例是一个小作业。 2,5,6,7 满足约束。


入力例 4

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

出力例 4

37

此输入示例是一个小作业。 2,3,5,6,7 满足约束。


入力例 5

8 8 2
1 2 1 5
5 6 3 1
2 4 10 18
3 5 3 1
1 3 4 2
5 6 2 2
2 5 2 3
6 8 1 1

出力例 5

25

相同 可能存在多条具有成对 (A_i,B_i) 的道路。

此输入示例是一个小作业。 2,4,5,6,7 满足约束。


入力例 6

6 10 100000
4 2 212037 752027141
2 5 667097 1571491
2 1 769275 576006950
1 2 711969 526189398
5 3 733555 206320177
3 4 364807 802102091
1 4 467240 183184247
3 5 44994 15991843
5 3 613192 782356546
4 6 832593 639529758

出力例 6

47546714005

此输入示例是一个小作业。 5,6,7 满足约束。