ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#6097
サブタスク

최장 여행 일정 2s 1024MB

問題

정올랜드에는 1부터 N까지 번호가 매겨진 N개의 마을과 M개의 단방향 도로이 있으며, 각 i번째 도로는 마을 a_i에서 출발하여 b_i로 도착하는 도로 번호가 l_i인 도로다.

길이 k의 여행 일정은 x_0번 마을에서 시작하는 x_0,x_1,…,x_k의 수열로 이루어진다. 이때, x_i번 마을에서 x_{i+1}번 마을로 이동하는 길이 존재하며, 무한한 길이의 여행 일정이 없음이 보장되고, 동일한 마을 쌍을 연결하는 도로는 둘 이상 존재하지 않는다.

정올이는 각 마을에서 시작하는 가장 긴 여행 일정을 알고 싶어한다. 시작하는 도시에 따라 여러 최장 여행 일정이 있을 수 있으며, 이 중에서도 도로 번호 순서가 사전적으로 최소인 여행 일정을 선호한다. 두 여행 목록의 길이가 같을 때 첫 번째 여행 일정이 두 번째 여행 일정보다 작은 요소를 가지고 있으면 첫 번째 여행 일정은 두 번째 여행 일정보다 사전적으로 작다.

각 마을에서 시작하는 것이 가능한 여행 일정 중 정올이가 가장 선호하는 여행 일정의 길이와 도로 레이블 합계를 출력하세요.


入力

첫 번째 줄에 두 정수 N과 M이 주어진다. (2≤N≤2⋅10^5, 1≤M≤4⋅10^5)

다음 M 줄에 a_i, b_i, l_i 세 정수가 주어진다. 이는 도로 번호가 l_i인 a_i에서 b_i로 이어지는 도로를 나타낸다. (1≤a_i,b_i≤N, 1≤l_i≤10^9)


出力

N개의 줄에 걸쳐 i번째 줄에는 i번 마을에서 시작하는 것이 가능한 여행 일정 중 정올이가 가장 선호하는 여행 일정의 길이와 도로 번호의 합계를 나타내는 두 정수를 공백으로 구분하여 출력한다.


部分問題

番号 点数 条件
#110点

모든 도로 번호는 동일하다

#220点

중복되는 도로 번호는 없다

#330点

N, M \le 5,000

#440点

추가 제약 조건 없음


例題 #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

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다.


例題 #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


出典

USACO 2023 December Gold

ログインしないとコードを書けません。