백준 25636: 소방차

문제 요약

ANA 도시는
$N$개의 교차로와,
$M$개의 양방향 도로로 이루어져 있고, 교차로는 $1$번부터 $N$번까지 번호가 매겨져 있다. $S$번 교차로에는 ANA 도시의 유일한 소방서가 위치하는데, 무겸이는 이곳에서 소방차 운전 기사로 일하고 있다. 무겸이는 소방차를 타고 화재가 발생한 교차로에 출동해서 화재를 진압한다.

소방차에는 물을 담을 수 있는 물탱크가 있어서 이곳에 담은 물을 화재를 진압하는데에 사용할 수 있다. 소방차는 소방서에서 물탱크가 빈 상태로 출동하지만, 이동 중에 교차로에 도착할 때마다 교차로에 설치된 소화전을 이용해서 물탱크에 물을 충전한다. 소방차가
$i$번째 교차로에 한 번 도착할 때마다 충전하는 물의 양은
$a_i$리터이며, 소방차는 소방서가 위치한 교차로에서 출동할 때나 화재가 발생한 교차로에 도착했을 때에도 물탱크에 물을 충전한다. 무겸이가 교차로에서 물을 충전하는데에는 시간이 걸리지 않고, 소방차의 물탱크의 용량에도 제한이 없다.

어느 날, $T$번 교차로에 화재가 발생했다. 무겸이는 소방차를 타고 화재가 발생한 교차로까지 최단 경로로 이동한다. 그런데 이러한 최단 경로는 여러 개가 있을 수 있다. 무겸이는 여러 개의 최단 경로 중에서 최대한 많은 양의 물을 가지고 도착할 수 있는 경로로 이동한다. 무겸이가 $T$번 교차로에 도착했을 때, 소방차의 이동 거리와 물탱크에 충전된 물의 양은 얼마일까?

문제 분류

• 그래프 이론
• 최단 경로
• 데이크스트라

문제 풀이

문제 자체는 길지만, 다익스트라의 가중치에 대해 공부할 수 있는 좋은 문제였다. 최단 경로로 탐색하되, 최단 경로의 길이가 같다면 누적 물탱크의 양이 되는 경로를 우선으로 탐색하도록 우선순위 큐의 조건을 조정해주면 된다.

풀이 코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m;
	static int a[];
	static boolean visited[];
	static List<Pair> e[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		n = Integer.parseInt(br.readLine());
		int u, v, w;
		a = new int[n + 1];
		visited = new boolean[n + 1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= n; i++)
			a[i] = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(br.readLine());
		e = new List[n + 1];
		for(int i = 1; i <= n; i++)
			e[i] = new ArrayList<>();
		for(int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken());
			v = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());
			e[u].add(new Pair(v, w));
			e[v].add(new Pair(u, w));
		}
		st = new StringTokenizer(br.readLine());
		u = Integer.parseInt(st.nextToken());
		v = Integer.parseInt(st.nextToken());
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(u, 0, a[u]));
		long level = 0, res = -1;
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			if(node.v == v) {
				level = node.w;
				res = node.a;
				break;
			}
			if(visited[node.v]) continue;
			visited[node.v] = true;
			for(Pair p : e[node.v]) {
				if(!visited[p.v])
					pq.offer(new Node(p.v, p.w + node.w, a[p.v] + node.a));
			}
		}
		if(res > 0)
			System.out.println(level + " " + res);
		else
			System.out.println(-1);
	}
}

class Pair {
	int v;
	long w;
	public Pair(int v, long w) {
		this.v = v;
		this.w = w;
	}
}

class Node implements Comparable<Node> {
	int v;
	long w;
	long a;
	public Node(int v, long w, long a) {
		this.v = v;
		this.w = w;
		this.a = a;
	}
	@Override
	public int compareTo(Node o) {
		int ret = Long.compare(this.w, o.w);
		return (ret != 0) ? ret : Long.compare(o.a, this.a);
	}
}