题目详情题解（0）讨论（0）提交记录（0）

AT_abc368_e.[ABC368E] Train Delay

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Atcoder 国有 11 到 NN 编号的 NN 个城市，以及 11 到 MM 编号的 MM 列火车在运行。
第 ii 列火车会在时刻 SiS_i 从城市 AiA_i 出发，并在时刻 TiT_i 到达城市 BiB_i。

给定正整数 X1X_1，请你确定 00 以上的整数 X2,…,XMX_2,\ldots,X_M，使得它们满足以下条件，并且 X2+…+XMX_2+\ldots+X_M 最小。

  • 条件：对于所有满足 1≤i,j≤M1\leq i,j\leq M 的组合 (i,j)(i,j)，如果「Bi=AjB_i=A_j 且 Ti≤SjT_i\leq S_j」，那么「Ti+Xi≤Sj+XjT_i+X_i\leq S_j+X_j」。
    • 也就是说，原本可以换乘的火车对，即使将每列火车 ii 的发车和到达时间都延迟 XiX_i，依然可以换乘。

可以证明，使 X2+…+XMX_2+\ldots+X_M 最小的 X2,…,XMX_2,\ldots,X_M 的取法是唯一的。

输入格式

输入按以下格式从标准输入读入。

NN MM X1X_1
A1A_1 B1B_1 S1S_1 T1T_1
⋮\vdots
AMA_M BMB_M SMS_M TMT_M

输出格式

请输出满足条件且使和最小的 X2,…,XMX_2,\ldots,X_M，按顺序用空格分隔。

输入输出样例

  • 输入#1

    3 6 15
1 2 10 20
1 2 20 30
2 3 25 40
2 3 35 50
3 1 15 30
3 1 45 60

    输出#1

    0 10 0 0 5

  • 输入#2

    10 9 100
1 10 0 1
10 2 1 100
10 3 1 100
10 4 1 100
10 5 1 100
10 6 1 100
10 7 1 100
10 8 1 100
10 9 1 100

    输出#2

    100 100 100 100 100 100 100 100

  • 输入#3

    4 4 10
1 2 0 1
1 2 0 10
2 3 100 200
2 4 100 200

    输出#3

    0 0 0

说明/提示

限制

  • 2≤N≤2×1052\leq N\leq 2\times 10^5
  • 2≤M≤2×1052\leq M\leq 2\times 10^5
  • 1≤Ai,Bi≤N1\leq A_i,B_i\leq N
  • Ai≠BiA_i\neq B_i
  • 0≤Si<Ti≤1090\leq S_i<T_i\leq 10^9
  • 1≤X1≤1091\leq X_1\leq 10^9
  • 所有输入均为整数

样例说明 1

第 11 列从城市 11 到 22 的火车到达时间延迟了 1515，变为 3535。
为了在城市 22 换乘到第 33 列火车，需要将第 33 列火车的发车时间延迟 1010，变为 3535 发车、5050 到达。
进一步，为了在城市 33 换乘到第 66 列火车，需要将第 66 列火车的发车时间延迟 55，变为 5050 发车。
其他火车无需延迟发车，原本可以换乘的火车之间依然可以换乘，因此 (X2,X3,X4,X5,X6)=(0,10,0,0,5)(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) 满足条件。
而且不存在比这更小的和，因此这就是答案。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页