백준 1504

모든 루트를 최적화해서 길을 찾아야 한다고 생각해서 모든 시작점에서 끝점으로 가는 루트를 업데이트했었는데,

한 level씩 추가로 탐색하는 것으로도 모든 case를 탐색할 수 있다. (inductively생각하면~)

그러면 모든 시작점을 고려할 필요 없이 첫점->중간점1->중간점2->끝점 의 루트만 생각하면 되므로(중간점1과 2는 바뀔 수 있지만)

3개의 시작점 첫점, 중간1점, 중간2점 만 고려하면 되므로 최대 3/800정도의 시간단축이 생길 듯.

물론 각 첫점을 search하는 데는, 모든 점을 업데이트 하지 않으니까 더 많은 루프를 돌아 최적을 찾아야 하므로

약 50~100배의 향상이 있을 것 같다.

import java.util.Scanner;

public class Main {
	public int[] routeFrom(int startindex, int[][] route){
		int n=route.length;
		boolean changed=true;
		for(;changed;) {
			changed=false;
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++) {
					if(route[startindex][i]!=0 && route[i][j]!=0 && 
						(route[startindex][j]>route[startindex][i]+route[i][j] || (route[startindex][j]==0 && startindex!=j))) {
						route[startindex][j]=route[startindex][i]+route[i][j];
						changed=true;
					}
//					System.out.printf("%d ", route[startindex][j]);
				}
//				System.out.println();
			}
//			System.out.println(startindex+"의 루프를 돌고 있습니다.");
		}
//		System.out.println("======================");
		return route[startindex];
	}
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		Main main=new Main();
		int N=sc.nextInt(), m=sc.nextInt();
		int[][] route=new int[N][N];
		for(int i=0;i<m;i++) {
			int from=sc.nextInt(), to=sc.nextInt(), distance=sc.nextInt(); // input route information
//			int from=(int)(Math.random()*N)+1, to=(int)(Math.random()*N)+1, distance=(int)(Math.random()*1000)+1; // input route information
			route[from-1][to-1]=distance;
			route[to-1][from-1]=distance;
		}
//		for(int i=0;i<N;i++) {
//			for(int j=0;j<N;j++) {
//				System.out.printf("%d ",route[i][j]);
//			}
//			System.out.println();
//		}
//		System.out.println("=====================");
		int mid1=sc.nextInt(), mid2=sc.nextInt();
//		int mid1=(int)(Math.random()*N)+1, mid2=(int)(Math.random()*N)+1;
		int[] routeFrom1=main.routeFrom(0,route);
		int[] routeFromMid1=main.routeFrom(mid1-1,route);
		int[] routeFromMid2=main.routeFrom(mid2-1,route);
		
		int startToMid1=routeFrom1[mid1-1];
		int mid1ToMid2=routeFromMid1[mid2-1];
		int mid2ToEnd=routeFromMid2[N-1];
		int startToMid2=routeFrom1[mid2-1];
		int mid2ToMid1=routeFromMid2[mid1-1];
		int mid1ToEnd=routeFromMid1[N-1];
		if(mid1==1 || mid1==N) {
			if(mid2==1 || mid2==N) {
				if(routeFrom1[N-1]==0) {
					System.out.println(-1);
				}
				else {
					System.out.println(routeFrom1[N-1]);
				}
			}
			else if(startToMid2==0 || mid2ToEnd==0){
				System.out.println(-1);
			}
			else {
				System.out.println(startToMid2+mid2ToEnd);
			}
		}
		else if(mid2==1 || mid2==N) {
			if(startToMid1==0 || mid1ToEnd==0) {
				System.out.println(-1);
			}
			else {
				System.out.println(startToMid1+mid1ToEnd);
			}
		}
		else if(startToMid1*mid1ToMid2*mid2ToEnd==0) {
			if(startToMid2*mid2ToMid1*mid1ToEnd==0) {
				System.out.println(-1);
			}
			else {
				System.out.println(startToMid2+mid2ToMid1+mid1ToEnd);
			}
		}
		else if(startToMid2*mid2ToMid1*mid1ToEnd==0) {
			System.out.println(startToMid1+mid1ToMid2+mid2ToEnd);
		}
		else if(startToMid1+mid1ToMid2+mid2ToEnd<startToMid2+mid2ToMid1+mid1ToEnd) {
			System.out.println(startToMid1+mid1ToMid2+mid2ToEnd);
		}
		else {
			System.out.println(startToMid2+mid2ToMid1+mid1ToEnd);
		}
	}

}