[알고리즘 문제풀이] 프로그래머스 - 합승 택시 요금 / JAVA(자바)

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

코딩테스트 연습 - 합승 택시 요금

/**
    플로이드 워셜 풀이
    
    1. 전체지점에서 전체 지점 이동 최소비용 구하기
    
    2. 시작지점에서 따로 가는 것을 초기값 지정
    
    3. 시작지점에서 중간지점까지 가는 비용 + 중간지점에서 a, 중간지점에서 b 더해서 최소비용 반환
**/

import java.util.*;

class Solution {
    
    public int solution(int n, int s, int a, int b, int[][] fares) {
        int answer = 0;
        
        int maxInt = 100_001*200;
        
        int[][] costs = new int[n+1][n+1];
        
        for(int i = 0; i <= n; i++){
            Arrays.fill(costs[i],maxInt);
            costs[i][i] = 0;
        }
        
        for(int[] fare : fares){
            int start = fare[0];
            int end = fare[1];
            int cost = fare[2];
            
            costs[start][end] = cost;
            costs[end][start] = cost;
        }
        
        for(int mid = 1; mid <= n; mid++){
            for(int i = 1; i <= n; i++){
                for(int j = 1; j <= n; j++){
                    costs[i][j] = Math.min(costs[i][j], costs[i][mid] + costs[mid][j]);
                }
            }
        }
        answer = maxInt;
        
        for(int i = 1; i <=n; i++){
            answer = Math.min(answer, costs[s][i] + costs[i][a] + costs[i][b]);
        }
        
        return answer;
    }
}