포션 택배
골드 III의견: 0
택배 로봇이 노드 \(S\)에서 노드 \(T\)까지 무방향 가중치 그래프를 따라 이동한다. 로봇은 출발 시 포션 \(K\)개를 가지고 있으며, 간선을 하나 지날 때마다 포션이 \(1\)개 소모된다. 포션이 \(0\)개이면 더 이상 이동할 수 없다.
그래프의 일부 노드에는 포션 스테이션이 있어서, 로봇이 그 노드에 도착하면 포션이 \(K\)개로 즉시 충전된다.
간선 비용의 합으로 정의되는 이동 비용을 최소화하면서 \(S\)에서 \(T\)까지 이동하는 최솟값 비용을 구하여라. 이동이 불가능하면 \(-1\)을 출력한다.
- \(2 \le N \le 1\,000\)
- \(1 \le M \le 5\,000\)
- \(1 \le K \le 20\)
- \(0 \le P \le N\)
- \(1 \le u, v \le N\), \(\;1 \le w \le 10^4\)
- \(1 \le S, T \le N\)
첫째 줄에 노드 수 \(N\), 간선 수 \(M\), 포션의 최대 개수 \(K\)가 공백으로 구분되어 주어진다.
둘째 줄에 포션 스테이션의 수 \(P\)가 주어진다.
셋째 줄에 포션 스테이션인 노드 번호 \(P\)개가 공백으로 구분되어 주어진다. \(P = 0\)이면 이 줄은 생략된다.
다음 \(M\)개의 줄에 간선 정보 \(u\), \(v\), \(w\)가 공백으로 구분되어 주어진다 (양방향, 비용 \(w\)).
마지막 줄에 출발 노드 \(S\)와 도착 노드 \(T\)가 공백으로 구분되어 주어진다.
\(S\)에서 \(T\)까지의 최소 이동 비용을 출력한다. 이동이 불가능하면 \(-1\)을 출력한다.
5 4 2
1
3
1 2 10
2 3 10
3 4 10
4 5 10
1 5
40
포션은 \(2\)개 있어 최대 \(2\)칸씩 이동한다. \(1 \to 2 \to 3\)(포션 스테이션, 충전) \(\to 4 \to 5\) 경로로 비용 \(40\)에 도달한다.
6 5 3
0
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
1 6
-1
포션 \(3\)개로 최대 \(3\)칸 이동 가능한데, 포션 스테이션이 없어 노드 \(4\)까지밖에 가지 못한다. 따라서 \(-1\)을 출력한다.
riseoj 작성
출처 Original
평가 및 의견
포션 택배
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
포션 택배