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

문제링크: www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

난 다익스트라를 조금만 응용해도 감을 못잡는 경우가 있는 것 같다.

최단경로 문제를 조금 더 풀어봐야겠다. 최단경로 문제는 재밌기도 하고.

어쨌든 위 문제는 시작점 세 군데에 대해 다익스트라를 수행하면서 정보를 저장했다.

1번 시작점에서 갈 수 있는 모든 최단거리

반드시 들러야 하는 두 곳을 시작점으로 갈 수 있는 최단거리를 저장했다.

이 과정에서 이미 저장되어 있을 최단거리 정보를 중복해서 탐색한다. 다른 방법이 있을 것 같아서

시도했지만 결국 포기했다.

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


public class Main {

	public static class Node implements Comparable<Node>{
		int dest;
		int weight;
		int first_visited;
		int second_visited;
		Node(){}
		Node(int d,int w){
			dest= d;
			weight = w;
		}
		Node(int d,int w, int first_visited,int second_visited){
			dest=d;
			weight=w;
			this.first_visited= first_visited;
			this.second_visited = second_visited;
		}
		@Override
		public int compareTo(Node o) {
			if(this.weight > o.weight) return 1;
			return 0;
		}
	}
	public static ArrayList<Node> adj[]; 
	public static int N,E;
	public static int first,second;
	public static int [][]dist_start;
	public static int [][]dist_first;
	public static int [][]dist_second;
	public static final int MAX = 987654321;
	public static void init(int[][] dist){
		for(int i=0;i<dist.length;i++){
			for(int j=0;j<dist[i].length;j++){
				if(i==j)continue;
				dist[i][j] = MAX;
			}
		}
	}
	
	public static int [][]dijkstra(int num){
		int [][] dist = new int[N+1][N+1];
		init(dist);
		PriorityQueue<Node> pq = new PriorityQueue<Node>();
		pq.offer(new Node(num,0));
		while(!pq.isEmpty()){
			Node cur = pq.poll();
			for(int i=0;i<adj[cur.dest].size();i++){
				Node next = adj[cur.dest].get(i);
				if(dist[num][next.dest] > cur.weight + next.weight){
					dist[num][next.dest] = cur.weight + next.weight;
					pq.offer(new Node(next.dest,cur.weight + next.weight));
				}
			}
		}
		
		return dist;
	}
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		adj = new ArrayList[N+1];
		for(int i=1;i<=N;i++) {
			adj[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 w = Integer.parseInt(st.nextToken());
			adj[s].add(new Node(e,w));
			adj[e].add(new Node(s,w));
		}
		st  = new StringTokenizer(br.readLine());
		first = Integer.parseInt(st.nextToken());
		second = Integer.parseInt(st.nextToken());
		
		dist_start = dijkstra(1);
		dist_first = dijkstra(first);
		dist_second = dijkstra(second);
		
		int ans = MAX;
		ans = Math.min(dist_start[1][first] + dist_first[first][second] + dist_second[second][N], 
				dist_start[1][second]+dist_second[second][first]+dist_first[first][N]);
		if(ans < MAX && ans > 0){
			System.out.println(ans);
		}else{
			System.out.println(-1);
		}
		
	}

}