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

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

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 Main_BOJ_1504 {
	static class Node implements Comparable<Node>{
		int id, cost;
		Node(int dest, int cost){
			this.id=dest;
			this.cost=cost;
		}
		@Override
		public int compareTo(Node o) {
			return this.cost-o.cost;
		}
	}
	static int N, E;
	static ArrayList<ArrayList<Node>> li=new ArrayList<>();
	static long answer=Long.MAX_VALUE;
	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());
		for (int i=0; i<N+1; i++) {
			li.add(new ArrayList<>());
		}
		for (int i = 0; i < E; i++) {
			st=new StringTokenizer(br.readLine());
			int a=Integer.parseInt(st.nextToken());
			int b=Integer.parseInt(st.nextToken());
			int c=Integer.parseInt(st.nextToken());
			li.get(a).add(new Node(b,c));
			li.get(b).add(new Node(a,c));
		}
		st=new StringTokenizer(br.readLine());
		int v1=Integer.parseInt(st.nextToken());
		int v2=Integer.parseInt(st.nextToken());
		process(v1, v2);
		if (answer!=Long.MAX_VALUE) {
			System.out.println(answer);
		}
		else {
			System.out.println(-1);
		}

	}
	private static void process(int v1, int v2) {
		long sum1=0, sum2=0;
		sum1=(dijkstra(1,v1)+dijkstra(v1, v2)+dijkstra(v2, N));
		sum2=(dijkstra(1,v2)+dijkstra(v2, v1)+dijkstra(v1, N));
		if (sum1<Integer.MAX_VALUE || sum2<Integer.MAX_VALUE) {
			answer=Math.min(sum1, sum2);
		}
	}
	private static long dijkstra(int start, int dest) {
		int[] dist=new int[N+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start]=0;
		PriorityQueue<Node> pq=new PriorityQueue<>();
		pq.add(new Node(start, 0));
		while (!pq.isEmpty()) {
			Node now=pq.poll();
			if (dist[now.id]<now.cost) continue;
			for (int i=0; i<li.get(now.id).size(); i++) {
				Node neighbor=li.get(now.id).get(i);
				if (dist[neighbor.id]>now.cost+neighbor.cost) {
					dist[neighbor.id]=now.cost+neighbor.cost;
					pq.add(new Node(neighbor.id, dist[neighbor.id]));
				}
			}
		}
		return dist[dest];
	}

}

다익스트라를 이용하는 코드.

난 6번 돌렸으나..(바보같은 선택), 3번만 돌려도 OK 다.

다익스트라는 출발지 고정일 때 쓴다. 

즉, 1->v1->v2->N, 1->v2->v1->N 이렇게 갈 수 있는 2가지 경우의 수가 있다.

 

1번에서 출발하는 경우(1->v1, 1->v2 일 때 사용 가능)

v1에서 출발하는 경우(v1->v2, v1->N 일 때 사용가능)

v2에서 출발하는 경우(v2->N, v2->v1 일 때 사용가능) 

 

이 3가지의 다익스트라를 구해줘서 최솟값을 구하면 된다.

 

주의할 점은, 경로가 없는 case가 나올 경우 Integer.MAX_VALUE 가 나올 것이므로, 두 경로 합이 모두 이 이상이 되면 -1을 출력해야 한다.

 

다익스트라: 출발지 고정임을 기억하고 풀것.