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

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

예제 입력 1

4 6
1 2 3
2 3 3
3 4 1
1 3 5
2 4 5
1 4 4
2 3

예제 출력 1

7

 

소스코드

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 {

	private static BufferedReader bf;
	private static StringTokenizer st;
	
	private static int N, E, A, B;
	private static boolean cannot;
	private static ArrayList<Node> [] node;
	private static int [] dist;
	
	static class Node implements Comparable<Node> {
		int val, cost;

		public Node(int val, int cost) {
			super();
			this.val = val;
			this.cost = cost;
		}

		@Override
		public String toString() {
			return "Node [val=" + val + ", cost=" + cost + "]";
		}

		@Override
		public int compareTo(Node o) {
			return this.cost-o.cost;
		}
		
		
	}
	
	public static void main(String[] args) throws IOException {

		bf=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(bf.readLine());
		N=Integer.parseInt(st.nextToken());
		E=Integer.parseInt(st.nextToken());
		node=new ArrayList[N+1];
		for(int i=1;i<=N;i++) node[i]=new ArrayList<>();
		
		dist=new int[N+1];
		
		
		for(int i=0;i<E;i++) {
			st=new StringTokenizer(bf.readLine());
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			int cost=Integer.parseInt(st.nextToken());
			node[start].add(new Node(end, cost));
            node[end].add(new Node(start,cost));
		}
		
		st=new StringTokenizer(bf.readLine());
		A=Integer.parseInt(st.nextToken());
		B=Integer.parseInt(st.nextToken());
		
		int []l1= {1,A,B,N};
		int []l2= {1,B,A,N};
		cannot=false;
		int result1=0;
		for(int i=0;i<3;i++) {	// 1 -> v1 -> v2 -> N
            if(l1[i]==l1[i+1]) continue;	// 반드시 거쳐가는 두 정점에 시작점이나 도착점이 포함된 경우는 거리가 0이므로 계산할 필요 없음
			if(cannot) {	// 경로가 없는 경우
				result1=Integer.MAX_VALUE;
				break;
			}
			result1+=dijkstra(l1[i],l1[i+1]);	// 경로가 존재하면 길이를 더해줌
		}
		cannot=false;
		int result2=0;
		for(int i=0;i<3;i++) {	// 1 -> v2 -> v1 -> N
            if(l2[i]==l2[i+1]) continue;	// 반드시 거쳐가는 두 정점에 시작점이나 도착점이 포함된 경우는 거리가 0이므로 계산할 필요 없음
			if(cannot) {	// 경로가 없는 경우
				result2=Integer.MAX_VALUE;
				break;
			}
			result2+=dijkstra(l2[i],l2[i+1]);	// 경로가 존재하면 길이를 더해줌
		}
		int result=Math.min(result1, result2);
		if(result==Integer.MAX_VALUE) System.out.println(-1);
		else System.out.println(result);
	}

	public static int dijkstra(int start, int end) {
		PriorityQueue<Node> pq=new PriorityQueue<>();
		pq.add(new Node(start,0));
		
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[1]=0;
		
		while(!pq.isEmpty()) {
			Node now=pq.poll();
			int val=now.val;
			int cost=now.cost;
			if(dist[val]<cost) continue;
			
			for(int i=0;i<node[val].size();i++) {
				int val2=node[val].get(i).val;
				int cost2=node[val].get(i).cost+cost;
				if(dist[val2]>cost2) {
					dist[val2]=cost2;
					pq.add(new Node(val2, cost2));
				}
			}
		}
		if(dist[end]==Integer.MAX_VALUE) cannot=true;
		return dist[end];
	}
}

전형적인 다익스트라 문제입니다.