(다익스트라) 백준 1504 - 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

입력

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

출력

7

 

JAVA 코드

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

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static ArrayList<Node>[] al;
    static int N,E;
    static int INF = 1000*200000; 
    
    static class Node implements Comparable<Node>{
    	int idx, cost;
    	Node(int idx, int cost){
    		this.idx = idx;
    		this.cost = cost;
    	}
    	
    	@Override
    	public int compareTo(Node o) {
    		if(this.cost < o.cost) return -1;
    		if(this.cost > o.cost) return 1;
    		return 0;
    	}
    }

    public static void main(String[] args) throws IOException{
    	st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	E = Integer.parseInt(st.nextToken());
    	
    	al = new ArrayList[N+1];
    	for(int i=1 ; i<N+1 ; i++) {
    		al[i] = new ArrayList<Node>();
    	}

    	for(int i=0 ; i<E ; i++) {
    		st = new StringTokenizer(br.readLine());
    		int s = Integer.parseInt(st.nextToken());
    		int e = Integer.parseInt(st.nextToken());
    		int c = Integer.parseInt(st.nextToken());
    		al[s].add(new Node(e,c));
    		al[e].add(new Node(s,c));
    	}
    	
    	st = new StringTokenizer(br.readLine());
		int mid1 = Integer.parseInt(st.nextToken());
		int mid2 = Integer.parseInt(st.nextToken());
		
		//1 -> mid1 -> mid2 -> N
		//1 -> mid2 -> mid1 -> N
		
		int init1 = dij(1,mid1);
		int MID = dij(mid1,mid2);
		int final1 = dij(mid2,N);
		
		int init2 = dij(1,mid2);
		int final2 = dij(mid1,N);
		
		int case1 = init1+MID+final1;
		int case2 = init2+MID+final2;
		
		if(case1 >= INF && case2 > INF)
			System.out.println(-1);
		else
			System.out.println(Math.min(case1, case2));
    }
    
    public static int dij (int start, int end) {
    	int[] cost = new int[N+1];
    	for(int i = 0 ; i<N+1 ; i++)
    		cost[i] = INF;
    	cost[start] = 0;
    	
    	PriorityQueue<Node> q = new PriorityQueue<>();
    	q.add(new Node(start,0));
    	
    	while(!q.isEmpty()) {
    		Node now = q.remove();
    		for(int i=0 ; i<al[now.idx].size(); i++) {
    			Node next = al[now.idx].get(i);
    			
    			if(cost[next.idx] > cost[now.idx] + next.cost) {
    				cost[next.idx] = cost[now.idx] + next.cost;
    				q.add(new Node(next.idx, cost[next.idx]));
    			}
    		}
    	}
    	return cost[end];
    }
}