USACO2023年12月美国计算机奥赛竞赛金奖组问题二—Minimum Longest Trip

Bessie is going on a trip in Cowland, which has N (2≤N≤2⋅10⁵) towns numbered from 1 to N and M (1≤M≤4⋅10⁵) one-way roads. The ith road runs from town a_i
to town b_i and has label li (1≤a_{i ,} b_i≤N, 1≤l_i≤109).

A trip of length k starting at town x₀ is a sequence of towns x₀,x₁,…,x_k, such that there is a road from town x_i to town x_i+1 for all 0≤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.

Output the length and sum of road labels of Bessie's preferred trip starting at each town.

INPUT FORMAT (pipe stdin):

The first line contains N and M.

The next M lines each contain three integers a_{i ,} b_i and l_i, denoting a road from a_i
to b_i with label l_i.

OUTPUT FORMAT (pipe stdout):

Output N lines. The ith should contain two space-separated integers, the length and sum of road labels of Bessie's preferred trip starting at town i.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 10
1 10
2 20

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 10
1 5
2 12

In the following explanation, we let represent the road from a_i to b_i with label l_i.

There are several trips starting from vertex 4, including and 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.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 10
1 5
2 7

SAMPLE INPUT:

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

SAMPLE OUTPUT:

0 0
1 5
1 10
2 7

SCORING:

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

扫码领取USACO试题答案+详细解析

咨询一对一备赛规划