시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 170 | 74 | 71 | 43.827% |
There is a directed graph $G$ with $N$ nodes and $M$ edges. Each node is numbered $1$ through $N$, and each edge is numbered $1$ through $M$. For each $i$ ($1 \le i \le M$), edge $i$ goes from vertex $u_i$ to vertex $v_i$ and has a unique color $c_i$.
A walk is defined as a sequence of edges $e_1$, $e_2$, $\cdots$, $e_{l}$ where for each $1 \le k < l$, $v_{e_k}$ (the tail of edge $e_k$) is the same as $u_{e_{k+1}}$ (the head of edge $e_{k+1}$). We can say a walk $e_1,\ e_2,\ \cdots,\ e_l$ starts at vertex $u_{e_1}$ and ends at vertex $v_{e_l}$. Note that the same edge can appear multiple times in a walk.
The color sequence of a walk $e_1,\ e_2,\ \cdots,\ e_l$ is defined as $c_{e_1},\ c_{e_2},\ \cdots,\ c_{e_l}$.
Consider all color sequences of walks of length at most $10^{100}$ from vertex $S$ to vertex $T$ in $G$. Write a program that finds the lexicographically minimum sequence among them.
The first line of the input contains four space-separated integers $N$, $M$, $S$, and $T$ ($1 \le N \le 100\,000$, $0 \le M \le 300\,000$, $1 \le S \le N$, $1 \le T \le N$, $S \neq T$).
Then $M$ lines follow: the $i$ ($1 \le i \le M$)-th of them contains three space-separated integers $u_i$, $v_i$ and $c_i$ ($1 \le u_i, v_i \le N$, $u_i \neq v_i$, $1 \le c_i \le 10^{9}$); it describes a directional edge from vertex $u_i$ to vertex $v_i$ with color $c_i$.
The graph doesn't have multiple edges or loops, and each edge has a unique color. Formally, for any $1 \le i < j \le M$, $c_i \neq c_j$ and $(u_i,\ v_i) \neq (u_j,\ v_j)$ holds.
If there is no walk from vertex $S$ to vertex $T$, print "IMPOSSIBLE". (without quotes)
Otherwise, let's say $a_1,\ a_2,\ \cdots,\ a_l$ is the lexicographically minimum sequence among all color sequences of length at most $10^{100}$ from vertex $S$ to vertex $T$.
3 3 1 3 1 2 1 2 3 7 1 3 5
1 7
3 4 1 3 1 2 1 2 1 2 2 3 7 1 3 5
TOO LONG
2 0 2 1
IMPOSSIBLE
Sequence $p_1, p_2, \cdots, p_{n}$ is lexicographically smaller than another sequence $q_1, q_2, \cdots, q_{m}$ if and only if one of the following holds:
University > KAIST > 2019 KAIST 9th ICPC Mock Competition G번
Contest > Open Cup > 2019/2020 Season > Stage 5: Grand Prix of Korea G번