레이팅 미적용베시에게 \(1\dots N\)으로 번호가 붙은 \(N\) (\(1\le N\le 2 \cdot 10^5\))개의 정점과 \(M\) (\(N - 1\le M\le 2 \cdot 10^5\))개의 간선을 가진 무향 그래프가 주어진다. 각 간선은 정점 \(u\)와 \(v\) 사이의 무향 간선을 나타내는 두 정수 \(u, v\) (\(1\le u, v \le N\))와, 간선에 부여된 값인 a..z 범위의 라틴 소문자 \(c\)로 표현된다. 주어지는 그래프는 연결 그래프임이 보장된다. 다중 간선이나 자기 루프가 있을 수 있다.
\(f(a, b)\)를 정점 \(a\)에서 시작하여 정점 \(b\)에서 끝나는 모든 경로에 대해 간선 값들을 이어 붙인 것 중 사전순으로 가장 작은 것으로 정의한다. 경로는 같은 간선을 두 번 이상 포함할 수 있다 (즉, 사이클이 허용된다).
각 \(i\) (\(1\le i \le N\))에 대해, \(f(1, i)\)의 길이를 구하도록 베시를 도와라. 길이가 유한하면 그 길이를 출력하고, 그렇지 않으면 \(-1\)을 출력한다.
Problem credits: Daniel Zhu and Yash Belani
SCORING
- 입력 3-4: 모든 문자가 a이다.
- 입력 5-8: 모든 문자가 a 또는 b이다.
- 입력 9-14: \(N,M\le 5000\)
- 입력 15-22: 추가 제약 없음.
Problem credits: Daniel Zhu and Yash Belani
첫째 줄에 독립적인 테스트의 수 \(T\) (\(1\le T\le 10\))가 주어진다. 각 테스트는 다음 형식으로 주어진다.
첫째 줄에 \(N\)과 \(M\)이 주어진다.
다음 \(M\)개의 줄에 각각 두 정수와 그 뒤에 라틴 소문자 하나가 주어진다.
모든 테스트에 걸친 \(N\)의 합과 \(M\)의 합이 각각 \(4\cdot 10^5\)를 넘지 않음이 보장된다.
각 테스트에 대해, 공백으로 구분된 \(N\)개의 정수를 새 줄에 출력한다.
2
1 0
2 2
1 1 a
2 1 b0
0 -1For the first test case, node 1 can be reached with an empty path, so the answer
is 0. In the second test case, node 2 cannot have a lexicographically smallest
path, since FJ can repeat the 'a' self-loop any number of times before moving to
node 2, producing arbitrarily long strings that are still lexicographically
minimal. Therefore, the answer for node 2 is -1.
2
7 7
1 2 a
1 3 a
2 4 b
3 5 a
5 6 a
6 7 a
7 4 a
4 3
1 2 z
2 3 x
3 4 y0 1 1 5 2 3 4
0 1 2 -1For the first test case, node 1 has distance 0. Nodes 2 and 3 are adjacent with
node 1, and they have distance 1. For nodes 4, 5, 6, and 7, it can be proven
that the lexicographically shortest path does not pass through the edge between
node 2 and 4.
For the second test case, node 4 again has no lexicographically smallest path,
since the string can be extended indefinitely while remaining lexicographically
minimal. Thus, its answer is -1.
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Second Contest > Gold