백준 1504번 :: 특정한 최단경로

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

✍ 문제 풀이

 

- 문제에서 정점은 물론 간선도 여러 번 이동할 수 있다고 하였다.

- 단, 특정 정점 2개를 반드시 거쳐야 한다고 명시하였다.

- 어떻게 생각하면 될까?

- 원래 거쳐야 하는 정점이 없다면, 1부터 N까지 다익스트라 1번만 실행하면 된다.

- But, 거쳐야 하는 정점이 있다면 쪼개서 다익스트라를 하면 된다.

• 1 -> v1 -> v2 -> N
• 1 -> v2 -> v1 -> N

- 1에서v1 / v1에서 v2 / v2에서 N까지로 다익스트라 3번 수행

- 나중에 합산해서 최단 경로를 구하면 된다.

- 다만, N까지 도달하지 못할 경우 -1을 출력

- 이때, INF를 설정하는데 있어서 주의해야 한다.  Integer.MAX_VALUE를 설정하면 오버플로우 발생!

- INF = 200,000(간선의 최대 갯수) * 1,000(가중치 최댓값) = 200,000,000

 

✍ 소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Q1504_특정한최단경로 {

	static int n, e;
	static ArrayList<ArrayList<Node>> list;
	static int vertex1, vertex2;
	static int[] dist; // 시작점에서 정점으로 가는 최단거리
	static boolean[] visited;
	static final int INF = 200000000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken()); // 정점의 개수
		e = Integer.parseInt(st.nextToken()); // 간선의 개수
		list = new ArrayList<>();
		dist = new int[n+1];
		visited = new boolean[n + 1];

		Arrays.fill(dist, INF);

		for(int i=0; i<=n; i++) {
			list.add(new ArrayList<>());
		}

		for(int i=0; i<e; i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());

			list.get(v1).add(new Node(v2, w));
			list.get(v2).add(new Node(v1,w));
		}

		st = new StringTokenizer(br.readLine());
		vertex1 = Integer.parseInt(st.nextToken());
		vertex2 = Integer.parseInt(st.nextToken());

		// 1 -> v1 -> v2 -> N
		int ans1 = 0;
		ans1 += dijkstra(1,vertex1);
		ans1 += dijkstra(vertex1,vertex2);
		ans1 += dijkstra(vertex2,n);

		// 1 -> v2 -> v1 -> N
		int ans2 = 0;
		ans2 += dijkstra(1,vertex2);
		ans2 += dijkstra(vertex2,vertex1);
		ans2 += dijkstra(vertex1,n);

		int result = (ans1 >= INF && ans2 >= INF) ? -1 : Math.min(ans1,ans2);

		System.out.println(result);

	}

	static class Node implements Comparable<Node> {
		int v;
		int weight;

		public Node(int v, int weight) {
			this.v = v;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node node) {
			return this.weight - node.weight;
		}
	}

	static int dijkstra(int v1, int v2) {

		Arrays.fill(dist, INF);
		Arrays.fill(visited, false);

		PriorityQueue<Node> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[n+1];
		pq.add(new Node(v1, 0));
		dist[v1] = 0;

		while(!pq.isEmpty()) {
			int current = pq.poll().v;
			visited[current] = true;

			for(Node node : list.get(current)) {
				if(visited[node.v]) continue;
				if(dist[current]+node.weight >= dist[node.v]) continue;

				dist[node.v] = dist[current]+node.weight;
				pq.add(new Node(node.v, dist[node.v]));
			}
		}

		return dist[v2];
	}
}