백준 1504

아래는 수정한 코드. 런타임 에러가 없어진 것으로 메모리 제한에는 걸리지 않지만 시간초과가 됨.

일단 C로 고쳐서 짜 보고 C에서도 시간초과가 뜨면 조금 더 수정해서 필요없는 계산을 날려야 할 듯.

한 단계를 거칠 때 모든 루트를 다 고려하는 것이 아니라 한 번에 한 루트의 최단거리를 계산하는 방향으로 잡게 될 듯.

아래는 약간 수정한 코드.

import java.util.Scanner;

public class Main {	
	public int[][] shortestRouteMtx(int[][] input){
		int n=input.length;
		int[][] route0=new int[n][n];
		int[][] route1=new int[n][n];
		boolean parity=true;
		route0=input;
		for(int i=0;i<n;i++) {
			route1=new int[n][n];
			parity=true;
			for(int j=0;j<n;j++) {
				for(int k=0;k<n;k++) {
					if(j==k) {
						route1[j][k]=0;
					}
					else {
						for(int l=0;l<n;l++) {
							if(route1[j][k]==0) {
								if((j==l || l==k) || (route0[j][l]!=0 && route0[l][k]!=0)) {
									route1[j][k]=route0[j][l]+route0[l][k];
								}
							}
							else if((j==l || l==k) || (route0[j][l]!=0 && route0[l][k]!=0) && route1[j][k]>route0[j][l]+route0[l][k]){
								route1[j][k]=route0[j][l]+route0[l][k];
							}
						}
					}
					if(parity && route0[j][k]!=route1[j][k]) {
						parity=false;
					}
				}
			}
			if(parity) {
				break;
			}
		}
		return route0;
	}

	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 a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt();
			route[a-1][b-1]=c;
			route[b-1][a-1]=c;
		}
		int mid1=sc.nextInt(), mid2=sc.nextInt();
		route=main.shortestRouteMtx(route);

		int startToMid1=route[0][mid1-1];
		int mid1ToMid2=route[mid1-1][mid2-1];
		int mid2ToEnd=route[mid2-1][N-1];
		int startToMid2=route[0][mid2-1];
		int mid2ToMid1=route[mid2-1][mid1-1];
		int mid1ToEnd=route[mid1-1][N-1];
		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);
		}
	}
}