천 번째 지름길
다이아몬드 I의견: 0
\(N\)개의 정점과 \(M\)개의 방향 간선으로 이루어진 방향 그래프가 있다. 각 간선에는 양의 길이가 있다.
출발 정점 \(s\)에서 도착 정점 \(t\)로 가는 워크(walk)란, \(s\)에서 시작해 간선을 따라 이동하여 \(t\)에서 끝나는 간선들의 나열이다. 같은 정점이나 같은 간선을 여러 번 지나가도 된다. 워크의 길이는 사용한 간선들의 길이 합이다.
서로 다른 워크(간선 나열이 다르면 다른 워크)들을 길이가 작은 순서대로 나열했을 때, \(1\)번째부터 \(K\)번째까지의 워크 길이를 차례대로 출력하라. \(s\)에서 \(t\)로 가는 워크가 \(K\)개 미만이라면, 남는 자리는 \(-1\)로 출력한다.
\(1 \le N \le 50{,}000\)
\(1 \le M \le 50{,}000\)
\(1 \le K \le 50{,}000\)
\(1 \le w \le 10^9\)
\(1 \le s, t \le N\). (자기 자신으로 가는 간선 \(u = v\)도 가능하다.)
첫 줄에 세 정수 \(N\), \(M\), \(K\)가 주어진다.
둘째 줄에 두 정수 \(s\), \(t\)가 주어진다.
이어서 \(M\)개의 줄에 각각 세 정수 \(u\), \(v\), \(w\)가 주어지며, \(u\)에서 \(v\)로 가는 길이 \(w\)의 방향 간선을 나타낸다.
한 줄에 \(K\)개의 정수를 공백으로 구분하여 출력한다. \(i\)번째 수는 \(i\)번째로 짧은 워크의 길이이며, 워크가 부족하면 \(-1\)이다.
3 3 5
1 3
1 2 2
2 3 3
2 2 1
5 6 7 8 9간선: 1->2(2), 2->3(3), 2->2(자기간선,1). s=1,t=3. 가장 짧은 워크 1->2->3 = 5. 자기간선을 한 번 돌면 1->2->2->3 = 6, 두 번이면 7, ... 5번째까지: 5 6 7 8 9.
3 1 3
1 3
1 2 5
-1 -1 -11->2 간선만 있고 3으로 가는 길이 없다. s=1, t=3으로 가는 워크가 하나도 없으므로 -1 -1 -1.
riseoj 작성
출처 Original
평가 및 의견
천 번째 지름길
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
천 번째 지름길