programmers_합승 택시 요금_java

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 20000001;
        
        int[][] path = new int[n+1][n+1];
        for(int i = 1; i<=n; i++){ // start
            for(int j = 1; j<=n; j++){ // end
                if(i == j) {
                    path[i][j] = 0;
                }
                else{
                    path[i][j] = 20000001;
                }
            }
        }
       
        for(int i = 0; i<fares.length; i++){
            path[fares[i][0]][fares[i][1]] = fares[i][2];
            path[fares[i][1]][fares[i][0]] = fares[i][2];
        }
        
        //플로이드 와샬
        for(int i = 1; i<=n; i++){ // mid
            for(int j = 1; j<=n; j++){ // start
                for(int k = 1; k<=n; k++){ // end
                    if(i == j || j == k || k == i) continue;
                    
                    path[j][k] = Math.min(path[j][i] + path[i][k], path[j][k]);
                }
            }
        }
        
        // 경유지가 없는 경우
        answer = path[s][a] + path[s][b];
        // 경유지가 있는 경우 확인
        for(int i = 1; i<=n; i++){
            answer = Math.min(path[s][i] + path[i][a] + path[i][b], answer);
        }
        
        return answer;
    }
}