수리 공방 경유
골드 IV의견: 0
리세 도시에는 \(N\)개의 거점과 \(M\)개의 단방향 도로가 있다. 당신은 거점 \(S\)에서 출발하여 거점 \(T\)에 도달해야 하는데, 도중에 수리 공방 \(K\)개 중 적어도 하나를 반드시 방문해야 한다.
수리 공방을 정확히 한 번 이상 방문하면서 \(S\)에서 \(T\)까지 이동하는 최소 총 비용을 구하여라.
도달 불가능하면 \(-1\)을 출력한다.
- \(2 \le N \le 200\,000\)
- \(0 \le M \le 300\,000\)
- \(1 \le K \le N\)
- \(1 \le S, T \le N\), \(S \ne T\)
- \(1 \le u, v \le N\), \(u \ne v\)
- \(1 \le w \le 10^9\)
첫째 줄에 거점의 수 \(N\), 도로의 수 \(M\), 출발 거점 \(S\), 도착 거점 \(T\)가 공백으로 구분되어 주어진다.
둘째 줄에 수리 공방의 수 \(K\)가 주어진다.
셋째 줄에 수리 공방이 위치한 거점 번호 \(K\)개가 공백으로 구분되어 주어진다. 모든 번호는 서로 다르다.
다음 \(M\)개의 줄에 도로 정보 \(u\ v\ w\)가 주어진다. 거점 \(u\)에서 거점 \(v\)로 비용 \(w\)로 이동할 수 있다.
수리 공방을 적어도 하나 방문하면서 \(S\)에서 \(T\)까지 이동하는 최소 비용을 출력한다. 불가능하면 \(-1\)을 출력한다.
5 7 1 5
1
3
1 2 2
2 3 3
3 5 4
1 3 10
1 4 1
4 5 1
1 5 20
9
공방은 거점 \(3\)뿐입니다. 출발지 \(1\)에서 공방 \(3\)까지 최단 경로는 \(1\to2\to3\): 비용 \(5\). 공방 \(3\)에서 목적지 \(5\)까지는 \(3\to5\): 비용 \(4\). 합계 \(9\). 직접 경로 \(1\to4\to5\): \(2\)는 공방을 거치지 않아 사용 불가. 따라서 정답은 \(9\)입니다.
4 4 1 4
2
2 3
1 2 1
2 4 2
1 3 3
3 4 1
3
공방 \(2\)를 경유하면 \(1\to2\to4\): 비용 \(3\), 공방 \(3\)을 경유하면 \(1\to3\to4\): 비용 \(4\). 최솟값은 \(3\)입니다.
3 2 1 3
1
3
1 2 5
2 3 5
10
공방 \(3\)은 목적지이기도 합니다. \(1\to2\to3\): 비용 \(10\). 정답은 \(10\)입니다. 공방이 목적지와 같을 수 있습니다.
riseoj 작성
출처 Original
평가 및 의견
수리 공방 경유
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
수리 공방 경유