문제
N개의 도시와 M개의 도로가 있을 때, 최대 K개의 도로를 포장(비용 0)할 수 있다. 1번에서 N번 도시까지의 최소 비용을 구하라.
입력
첫째 줄에 N, M, K, 이후 M줄에 (도시, 도시, 비용)이 주어진다.
출력
1번에서 N번까지의 최소 비용을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 4 1 1 2 10 2 4 10 1 3 1 3 4 100 | 1 |
풀이
다익스트라에 포장 횟수를 상태로 추가하여 cost[node][포장횟수]로 최단 경로를 구한다.
cost[i][j]: i번 노드에 j번 포장하여 도달하는 최소 비용- 우선순위 큐에서 현재 노드를 꺼낸 뒤 두 가지 전이를 시도한다
- 포장하지 않는 경우:
cost[next][cnt]를 비용 추가로 갱신 - 포장하는 경우 (cnt가 K 미만):
cost[next][cnt+1]을 비용 0으로 갱신 - N번 노드의
cost[N][0..K]중 최솟값이 답이다
핵심 아이디어: 상태를 (노드, 포장횟수)로 확장한 다익스트라로, K번의 포장 기회를 최적으로 분배한다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day451BOJ1162도로포장 {
static int N, M, K;
static List<Node>[] map;
static long[][] cost;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
cost = new long[N + 1][K + 1];
map = new ArrayList[N + 1];
for (int i = 1; i <= N; i++)
map[i] = new ArrayList<>();
for (int i = 1; i <= M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
map[a].add(new Node(b, 0, c));
map[b].add(new Node(a, 0, c));
}
dijkstra(1);
System.out.println(Arrays.stream(cost[N]).min().getAsLong());
}
static void dijkstra(int start) {
for (int i = 1; i <= N; i++)
Arrays.fill(cost[i], Long.MAX_VALUE);
cost[start][0] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0, 0));
while (!pq.isEmpty()) {
Node now = pq.poll();
if (now.cost > cost[now.node][now.cnt])
continue;
for (Node next : map[now.node]) {
if (now.cnt < K && cost[next.node][now.cnt + 1] > cost[now.node][now.cnt]) {
cost[next.node][now.cnt + 1] = cost[now.node][now.cnt];
pq.add(new Node(next.node, now.cnt + 1, cost[next.node][now.cnt + 1]));
}
if (cost[next.node][now.cnt] > cost[now.node][now.cnt] + next.cost) {
cost[next.node][now.cnt] = cost[now.node][now.cnt] + next.cost;
pq.add(new Node(next.node, now.cnt, cost[next.node][now.cnt]));
}
}
}
}
static class Node implements Comparable<Node> {
int node, cnt;
long cost;
@Override
public int compareTo(Node o) {
return (int) (this.cost - o.cost);
}
public Node(int node, int cnt, long cost) {
this.node = node;
this.cnt = cnt;
this.cost = cost;
}
}
}복잡도
- 시간: O(K * M * log(N*K)) - 확장된 다익스트라
- 공간: O(N*K)