#PU1354. USACO 2023 December Contest, Gold — Problem 2. Minimum Longest Trip

    ID: 1290 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:dec23来源:usaco.orgscoring:equal_test_cases树上算法

USACO 2023 December Contest, Gold — Problem 2. Minimum Longest Trip

USACO 2023 December Contest, Gold — Problem 2. Minimum Longest Trip

题目描述

Bessie is going on a trip in Cowland, which has NN (2≤N≤2⋅1052\le N\le 2\cdot 10^5) towns numbered from 11 to NN and MM (1≤M≤4⋅1051\le M\le 4\cdot 10^5) one-way roads. The iith road runs from town aia_i to town bib_i and has label lil_i (1≤ai,bi≤N1\le a_i,b_i\le N, 1≤li≤1091\le l_i\le 10^9). A trip of length kk starting at town x0x_0 is a sequence of towns x0,x1,…,xkx_0, x_1, \ldots, x_k, such that there is a road from town xix_i to town xi+1x_{i+1} for all 0≤i<k0\le i < k. It is guaranteed that there are no trips of infinite length in Cowland, and that no two roads connect the same pair of towns. For each town, Bessie wants to know the longest possible trip starting at it. For some starting towns, there are multiple longest trips - out of these, she prefers the trip with the lexicographically minimum sequence of road labels. A sequence is lexicographically smaller than another sequence of the same length if, at the first position in which they differ, the first sequence has a smaller element than the second sequence.

输入格式

The first line contains NN and MM. The next MM lines each contain three integers aia_i, bib_i, and lil_i, denoting a road from aia_i to bib_i with label lil_i.

输出格式

(见题面原文)

数据范围

Inputs 5-6: All labels are the same. Inputs 7-8: All labels are distinct. Inputs 9-10: N,M≤5000N,M\le 5000 Inputs 11-20: No additional constraints. Problem credits: Claire Zhang and Spencer Compton

样例

样例 1

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

样例 2

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
In the following explanation, we let $a_i\overset{l_i}\to b_i$ represent the
road from $a_i$ to $b_i$ with label $l_i$.
There are several trips starting from vertex $4$, including
$4 \overset{4}\to 3\overset{5}\to 1$, $4\overset{1}\to 1$, and
$4\overset{2}\to 2\overset{10}\to 1$. Of these trips,
$4 \overset{4}\to 3\overset{5}\to 1$ and $4\overset{2}\to 2\overset{10}\to 1$
are the longest. These trips each have length 2, and their road label sequences
are $[4,5]$ and $[2,10]$, respectively. $[2,10]$ is the lexicographically
smaller sequence, and its sum is $12$.

样例 3

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

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