페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#6097
서브태스크

최장 여행 일정 2s 1024MB

문제

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

길이 k의 여행 일정이란 x_0번 마을에서 시작하는 x_0,x_1,…,x_k의 수열로 이루어진다. 이때, 모든 0 \le i \le 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

로그인해야 코드를 작성할 수 있어요.