[programmers]2021 KAKAO BLIND RECRUITMENT-タクシー運賃

アイデア

正しい(効率100)

Java Code

import java.util.Arrays;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int road = fares.length;
		int[][] reFares = new int[n+1][n+1];
		for(int i=0; i<n+1; i++) {
			Arrays.fill(reFares[i], 1000001);
		}
		for(int i=1; i<n+1; i++) {
			reFares[i][i] = 0;
		}
		
		for(int i=0; i<road; i++) {
			reFares[fares[i][0]][fares[i][1]] = fares[i][2];
			reFares[fares[i][1]][fares[i][0]] = fares[i][2];
		}
		
		for(int i=1; i<n+1; i++) {//경
			for(int j=1; j<n+1; j++) {//출
				for(int k=1; k<n+1; k++) {//도
					if(reFares[j][k] > reFares[j][i]+reFares[i][k]) {
						reFares[j][k] = reFares[j][i]+reFares[i][k];
					}
				}
			}
		}
		
		int answer = reFares[s][a]+reFares[s][b];
		for(int i=1; i<n+1; i++) {//경
			if(answer > reFares[s][i] + reFares[i][a] + reFares[i][b]) {
				answer = reFares[s][i] + reFares[i][a] + reFares[i][b];
			}
		}
        
        return answer;
    }
}