[백준 1504] 특정한 최단 경로(Java)

1. 문제

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

2. 풀이

3. 코드

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

public class Main {

	static class Edge implements Comparable<Edge> {
		int to, weight;

		public Edge(int to, int weight) {
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			return Integer.compare(this.weight, o.weight);
		}
	}

	static final int INF = 200000000;
	static PriorityQueue<Edge> pq;
	static ArrayList<ArrayList<Edge>> list = new ArrayList<>();
	static int[] visited;
	static boolean[] check;
	static int N, M, start, end;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// br = new BufferedReader(new StringReader(src));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 정점
		M = Integer.parseInt(st.nextToken()); // 간선

		visited = new int[N + 1];
		check = new boolean[N + 1];
		Arrays.fill(visited, INF);

		for (int i = 0; i <= N; i++) {
			list.add(new ArrayList<>());
		}
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			list.get(from).add(new Edge(to, weight));
			list.get(to).add(new Edge(from, weight));
		}
		st = new StringTokenizer(br.readLine());
		int v1 = Integer.parseInt(st.nextToken());
		int v2 = Integer.parseInt(st.nextToken());

		int result1 = 0;
		result1 += dijkstra(1, v1);
		result1 += dijkstra(v1, v2);
		result1 += dijkstra(v2, N);
		int result2 = 0;
		result2 += dijkstra(1, v2);
		result2 += dijkstra(v2, v1);
		result2 += dijkstra(v1, N);

		int result = Math.min(result1, result2);
		if (result >= INF)
			System.out.println(-1);
		else
			System.out.println(result);

	}

	public static int dijkstra(int start, int end) {
		Arrays.fill(visited, INF);
		Arrays.fill(check, false);

		pq = new PriorityQueue<>();
		visited[start] = 0;
		pq.offer(new Edge(start, 0));

		while (!pq.isEmpty()) {
			Edge now = pq.poll();

			if (!check[now.to]) {
				check[now.to] = true;
				for (Edge next : list.get(now.to)) {
					if (!check[next.to] && visited[next.to] > visited[now.to] + next.weight) {
						visited[next.to] = visited[now.to] + next.weight;
						pq.offer(new Edge(next.to, visited[next.to]));
					}
				}
			}

		}
		return visited[end];
	}

	static String src = 
        "4 6\r\n" 
        + "1 2 3\r\n" 
        + "2 3 3\r\n" 
        + "3 4 1\r\n" 
        + "1 3 5\r\n" 
        + "2 4 5\r\n" 
        + "1 4 4\r\n"
		+ "2 3";
}

반응형