1504 cpp

cpp로 짰으나 여전히 시간 초과.

#include<stdio.h>
#define MAX_COL 800;
void shortestRouteMtx(int route[][MAX_COL], int size){
	bool unchanged=true;
	int unchangedCheck=0;
	for(int i=0;i<size;i++){
		unchanged=true;
		for(int j=0;j<size;j++){
			for(int k=0;k<size;k++){
				unchangedCheck=route[j][k];
				if(j==k){
					route[j][k]=0;
				}
				else{
					for(int l=0;l<size;l++){
						if(route[j][l]!=0 && route[l][k]!=0){
							if(route[j][k]==0 || (route[j][k]>route[j][l]+route[l][k] && route[j][k]!=0)){
								route[j][k]=route[j][l]+route[l][k];
							}
						}
					}
				}
				if(unchanged){
					unchanged=(unchangedCheck==route[j][k]);
				}
			}
		}
		if(unchanged){
			break;
		}
	}
	return;
}
int main(){
	int n=0, k=0;
	scanf("%d",&n);
	scanf("%d",&k);
	int route[n][MAX_COL];
	for(int i=0;i<n;i++){
		for(int j=0;j<j++){
			route[i][j]=0;
		}
	}
	int start,end,distance;
	for(int i=0;i<k;i++){
		scanf("%d",&start);
		scanf("%d",&end);
		scanf("%d",&distance);
		route[start-1][end-1]=distance;
		route[end-1][start-1]=distance;
	}
	shortestRouteMtx(route,n);
	int mid1,mid2;
	scanf("%d",&mid1);
	scanf("%d",&mid2);
	
	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) {
			printf("%d",-1);
		}
		else {
			printf("%d",startToMid2+mid2ToMid1+mid1ToEnd);
		}
	}
	else if(startToMid2*mid2ToMid1*mid1ToEnd==0) {
		printf("%d",startToMid1+mid1ToMid2+mid2ToEnd);
	}
	else if(startToMid1+mid1ToMid2+mid2ToEnd<startToMid2+mid2ToMid1+mid1ToEnd) {
		printf("%d",startToMid1+mid1ToMid2+mid2ToEnd);
	}
	else {
		printf("%d",startToMid2+mid2ToMid1+mid1ToEnd);
	}
	return 0;
}