Minimum Longest Trip

题目描述

Bessie 要去牛国（Cowland）旅行。牛国有 $N$（$2\le N\le 2\cdot 10^5$）个城镇，编号从 $1$ 到 $N$，以及 $M$（$1\le M\le 4\cdot 10^5$）条单向道路。 第 $i$ 条道路从城镇 $a_i$ 通向城镇 $b_i$，并带有标号 $l_i$（$1\le a_i,b_i\le N$, $1\le l_i\le 10^9$）。 从城镇 $x_0$ 出发、长度为 $k$ 的一次旅行（trip）是一个城镇序列 $x_0, x_1, \ldots, x_k$，满足对所有 $0\le i < k$，都存在一条从城镇 $x_i$ 到城镇 $x_{i+1}$ 的道路。 保证牛国中不存在长度无限的旅行，并且任意两座城镇之间不会有多条道路连接相同的有序对（即不存在两条道路连接同一对起点和终点）。 对每个城镇，Bessie 想知道从该城镇出发所能进行的最长旅行。 对于某些起点城镇，可能存在多条最长旅行——在这些最长旅行中，她更偏好道路标号序列按字典序最小的那一条。对于长度相同的两个序列，如果在它们第一次出现不同的位置上，第一个序列的元素更小，则称第一个序列的字典序更小。 请输出从每个城镇出发、Bessie 偏好的旅行的长度与道路标号之和。

输入格式

第一行包含 $N$ 和 $M$。 接下来 $M$ 行每行包含三个整数 $a_i$、$b_i$ 和 $l_i$，表示一条从 $a_i$ 到 $b_i$、标号为 $l_i$ 的道路。

输出格式

输出 $N$ 行。第 $i$ 行应包含两个用空格分隔的整数：从城镇 $i$ 出发、Bessie 偏好的旅行的长度，以及道路标号之和。

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

0 0
1 10
1 10
2 20

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

0 0
1 10
1 5
2 12

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

0 0
1 10
1 5
2 7

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

0 0
1 5
1 10
2 7

提示

在下面的解释中，我们用 $a_i\overset{l_i}\to b_i$ 表示从 $a_i$ 到 $b_i$、标号为 $l_i$ 的道路。 从点 $4$ 出发有若干种旅行，包括 $4 \overset{4}\to 3\overset{5}\to 1$、$4\overset{1}\to 1$，以及 $4\overset{2}\to 2\overset{10}\to 1$。在这些旅行中，$4 \overset{4}\to 3\overset{5}\to 1$ 和 $4\overset{2}\to 2\overset{10}\to 1$ 是最长的。它们的长度都为 2，对应的道路标号序列分别为 $[4,5]$ 和 $[2,10]$。$[2,10]$ 的字典序更小，其标号和为 $12$。 SCORING: Inputs 5-6: 所有标号都相同。 Inputs 7-8: 所有标号互不相同。 Inputs 9-10: $N,M\le 5000$ Inputs 11-20: 无额外限制。 题目出题人：Claire Zhang 和 Spencer Compton

标签: USACO|2023|Gold

来源

USACO|2023|Gold