백준 19701: 소 운전한다.

문제 요약

소들이 사는 대한민국에는 도시가
$V$개 있고, 두 도시를 양방향으로 잇는 고속도로가 $E$개 있다. 물론 소들은 $1$번 도시에 산다.
베시가 여행갈 수 있는 $2$번에서 $N$번까지의 각 도시에 대해, 경로와 들를 휴게소를 잘 골라서 $1$번 도시에서 이 도시로 가는 데 걸리는 시간에서 가는 도중에 휴게소를 적절히 하나 들러서 먹는 돈까스의 맛을 뺀 값의 최솟값을 구하라. 물론, 돈까스를 먹는 시간은 가는 데 걸리는 시간에 포함하지 않는다.

문제 분류

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

문제 풀이

어떤 간선을 통해 정점을 방문할 때, 해당 간선의 돈까스를 먹느냐/먹지 않느냐 두 가지 경우로 나누어 가상의 정점을 추가할 수 있다.
우선, 기본적으로 내가 방문한 간선의 돈까스를 먹지 않을 수 있다. 그러나 내가 돈까스를 먹지 않은 상태라면 현 간선의 돈까스를 먹을 수 있다. 이를 이용해서 다익스트라를 이용해 정점을 방문하고 그 답을 저장한다. 마지막에 각 정점 별 답을 출력

풀이 코드

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

public class Main {
	static int n, m;
	static long res[][];
	static List<Edge> e[];
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		n = Integer.parseInt(st.nextToken());
		int u, v, w, k;
		res = new long[n + 1][2];
		m = Integer.parseInt(st.nextToken());
		e = new List[n + 1];
		for(int i = 1; i <= n; i++) {
			e[i] = new ArrayList<>();
			res[i][0] = Long.MAX_VALUE;
			res[i][1] = Long.MAX_VALUE;
		}
		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());
			k = Integer.parseInt(st.nextToken());
			e[u].add(new Edge(v, w, k));
			e[v].add(new Edge(u, w, k));
		}
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(1, 0, 0));
		res[1][0] = 0;
		while(!pq.isEmpty()) {
			Node node = pq.poll();
			int v2 = (node.k > 0) ? 1 : 0;
			if(res[node.v][v2] < node.w - node.k) continue;
			for(Edge edge : e[node.v]) {				
				if(res[edge.v][v2] > node.w + edge.w - node.k) {
					res[edge.v][v2] = node.w + edge.w - node.k;
					pq.offer(new Node(edge.v, (long)node.w + edge.w, node.k));
				}
				if(v2 == 0) {
					if(res[edge.v][1] > node.w + edge.w - edge.k) {
						res[edge.v][1] = node.w + edge.w - edge.k;
						pq.offer(new Node(edge.v, (long)node.w + edge.w, edge.k));
					}
				}
			}
		}
		for(int i = 2; i <= n; i++)
			sb.append(res[i][1]).append("\n");
		System.out.println(sb);
	}
}

class Edge {
	int v;
	int w;
	int k;
	public Edge(int v, int w, int k) {
		this.v = v;
		this.w = w;
		this.k = k;
	}
}

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