[백준] 1504번. 특정한 최단 경로 (java, 다익스트라, 최단 경로)

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

1-> a -> b -> n 경로와 

1-> b -> a -> n 경로 중 작은 것이 답이다.

중간에 이어지는 선이 없으면 경로가 없는 것이다.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
	int node;
	int cost;
	public Edge(int node, int cost) {
		super();
		this.node = node;
		this.cost = cost;
	}
	@Override
	public int compareTo(Edge o) {
		return this.cost-o.cost;
	}
	
}

public class Main {
	static int n,e,a,b;
	static ArrayList<Edge> list[];
	static int[][] dist;
	static int answer=Integer.MAX_VALUE;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		e=sc.nextInt();
		list=new ArrayList[n+1];
		for (int i = 1; i <=n; i++) {
			list[i]=new ArrayList<>();
		}
		dist=new int[n+1][n+1];
		for (int i = 1; i <=n; i++) {
			Arrays.fill(dist[i], -1);
		}
		for (int i = 0; i <e; i++) {
			int x=sc.nextInt();
			int y=sc.nextInt();
			int cost=sc.nextInt();
			list[x].add(new Edge(y,cost));
			list[y].add(new Edge(x,cost));
		}
		
		a=sc.nextInt();
		b=sc.nextInt();
		
		solve();
		
		System.out.println(answer==Integer.MAX_VALUE?-1:answer);
		
	}
	private static void solve() {

		while(true) {
			int temp1=go(1,a);
			if(temp1==-1)break;
			int temp2=go(a,b);
			if(temp2==-1)break;
			int temp3=go(b,n);
			if(temp3==-1)break;
			int sum=temp1+temp2+temp3;
			answer=sum;
			break;
		}
		
		while(true) {
			int temp1=go(1,b);
			if(temp1==-1)break;
			int temp2=go(b,a);
			if(temp2==-1)break;
			int temp3=go(a,n);
			if(temp3==-1)break;
			int sum=temp1+temp2+temp3;
			if(answer>sum)answer=sum;
			break;
		}
		
	}
	private static int go(int start,int end) {

			PriorityQueue<Edge> pq=new PriorityQueue<>();
			pq.add(new Edge(start,0));
			while(pq.size()!=0) {
				Edge temp=pq.poll();
				int cur=temp.node;
				int cost=temp.cost;
				if(dist[start][cur]==-1) {
					dist[start][cur]=cost;
					for(Edge e:list[cur]) {
						int total=e.cost+cost;
						int next=e.node;
						pq.add(new Edge(next,total));
					}
				}
			}
		
		return dist[start][end];
	}
	
	
}