Lexicographically Smallest Path
골드 I의견: 0
Bessie is given an undirected graph with \(N\) (\(1\le N\le 2 \cdot 10^5\)) vertices
labeled \(1\dots N\) and \(M\) edges (\(N - 1\le M\le 2 \cdot 10^5\)). Each edge is
described by two integers \(u, v\) (\(1\le u, v \le N\)) describing an undirected
edge between nodes \(u\) and \(v\) and a lowercase Latin letter \(c\) in the range a..z that is the
value on the edge. The graph given is guaranteed to be connected. There may be
multiple edges or self-loops.
Define \(f(a, b)\) as the lexicographically smallest concatenation of edge values
over all paths starting from node \(a\) and ending at node \(b\). A path may contain
the same edge more than once (i.e., cycles are allowed).
For each \(i\) (\(1\le i \le N\)), help Bessie determine the length of \(f(1, i)\).
Output this length if it is finite, otherwise output \(-1\).
Problem credits: Daniel Zhu and Yash Belani
SCORING
- Inputs 3-4: Every character is a.
- Inputs 5-8: Every character is a or b.
- Inputs 9-14: \(N,M\le 5000\)
- Inputs 15-22: No additional constraints.
Problem credits: Daniel Zhu and Yash Belani
The first line contains \(T\) (\(1\le T\le 10\)), the number of independent tests.
Each test is specified in the following format:
The first line contains \(N\) and \(M\).
The next \(M\) lines each contain two integers followed by a lowercase Latin
character.
It is guaranteed that neither the sum of \(N\) nor the sum of \(M\) over all tests
exceeds \(4\cdot 10^5\).
For each test, output \(N\) space-separated integers on a new line.
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
평가 및 의견
Lexicographically Smallest Path
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Lexicographically Smallest Path