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

[문제링크]

1504번: 특정한 최단 경로

0. 1번 노드에서 v1,v2를 거쳐 N번 노드로 이동하는 방법은 2가지이다

  - v1을 먼저 방문 : 1-v1-v2-N

  - v2를 먼저 방문 : 1-v2-v1-N

  - 조건상 두 지점간 거리의 최댓값은 800개의 노드 가 1000 길이의 길로 연결됬을 경우인 799K이다

 

1. 1번노드, v1번 노드, v2번 노드에서 각각 다익스트라를 돌려, 다른 노드로 가는 최솟값을 찾는다

 

2. 다익스트라 계산 후 1-v1-v2-N 과 1-v2-v1-N 두 방법 중 cost가 작은것을 찾는다

 

3. 이론상 최대치가 약 80만이므로, 1-v1 / v1-v2 / v2-N 3번의 이동이 다 최대 cost에 가깝다고 해도 총 cost는 240만보다 작다

  - cost가 300만 이상의 결과가 나왔다면 경로가 존재하지 않아 초깃값이 계산된 경우이므로 -1을 출력한다

  - 그 외라면 구한 cost를 출력한다

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int n = pint(st.nextToken());
		int m = pint(st.nextToken());

		int[][]graph = new int[n+1][n+1];
		
		for (int i = 0; i < m; i++) {
			st=new StringTokenizer(br.readLine()," ");
			int n1 = pint(st.nextToken());
			int n2 = pint(st.nextToken());
			int c = pint(st.nextToken());
			graph[n1][n2]=c;
			graph[n2][n1]=c;
		}
		st=new StringTokenizer(br.readLine()," ");
		int n1 = pint(st.nextToken());
		int n2 = pint(st.nextToken());
	
		//다익스트라 준비물 * 3
		int[]dilk1=new int[n+1];
		int[]dilkn1=new int[n+1];
		int[]dilkn2=new int[n+1];
		Arrays.fill(dilk1, 3000000);
		Arrays.fill(dilkn1, 3000000);
		Arrays.fill(dilkn2, 3000000);
		
		boolean[] isV=new boolean[n+1];
		boolean[] isVn1=new boolean[n+1];
		boolean[] isVn2=new boolean[n+1];
		dilk1[1]=0;
		dilkn1[n1]=0;
		dilkn2[n2]=0;
		
		for (int i = 0; i < n; i++) {
			//아직 방문 안한 노드 중 가장 가까운 노드 탐색
			int min=Integer.MAX_VALUE, minnode=0;
			int minn1=Integer.MAX_VALUE, minnoden1=0;
			int minn2=Integer.MAX_VALUE, minnoden2=0;
			for (int j = 1; j <= n; j++) {
				if(!isV[j] && dilk1[j]<min) {
					min=dilk1[j];
					minnode=j;
				}if(!isVn1[j] && dilkn1[j]<minn1) {
					minn1=dilkn1[j];
					minnoden1=j;
				}if(!isVn2[j] && dilkn2[j]<minn2) {
					minn2=dilkn2[j];
					minnoden2=j;
				}
			}
			//해당 노드 방문처리
			isV[minnode]=true;
			isVn1[minnoden1]=true;
			isVn2[minnoden2]=true;
			
			for (int j = 1; j <= n; j++) {
				//아직 방문 안한 노드에 대해 cost 업데이트
				if(!isV[j] && graph[minnode][j]!=0) {
					dilk1[j]=Math.min(dilk1[j], dilk1[minnode]+graph[minnode][j]);
				}
				if(!isVn1[j] && graph[minnoden1][j]!=0) {
					dilkn1[j]=Math.min(dilkn1[j], dilkn1[minnoden1]+graph[minnoden1][j]);
				}
				if(!isVn2[j] && graph[minnoden2][j]!=0) {
					dilkn2[j]=Math.min(dilkn2[j], dilkn2[minnoden2]+graph[minnoden2][j]);
				}
			}
			
		}
		
		//1->n1->n2->n
		int cost=3000000;
		
		cost = Math.min(dilk1[n1]+dilkn1[n2]+dilkn2[n], dilk1[n2]+dilkn2[n1]+dilkn1[n]);
		if(cost>=3000000)System.out.println(-1);
		else System.out.println(cost);
		
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면