합승 택시 요금

합승한다는것에만 초점을 두고 생각하다가 막혔다

합승해서 이동하는걸 어떻게 처리해야 하는거지 이생각만 한거 같다

결국 S에서 중간지점 M 으로 같이 이동했다는건 S에서M으로가는 거리가 최단거리가 되는것을 구하면 되는것이라는 생각의 전환을 못한거 같다 SM + AM + BM 이렇게 하면 되므로

플로이드 워셜을 사용하면 된다.

import java.util.*;

class Solution {
    public int solution(int n, int s, int a, int b, int[][] fares) {
        
        int[][] fw = new int[n+1][n+1];
        final int MAX = 200 * 100000 + 1;
        for(int i = 1; i <= n; ++i)
        {
            Arrays.fill(fw[i], MAX);
            fw[i][i] = 0;
        }
        
        for(int i = 0; i < fares.length; ++i)
        {     
            int st = fares[i][0];
            int dest = fares[i][1];
            int dist = fares[i][2];
            
            fw[st][dest] = dist;
            fw[dest][st] = dist;
        }
        
        for(int m = 1; m <= n; ++m)
        {
            for(int i = 1; i <= n; ++i)
            {
                for(int j = 1; j <= n; ++j)
                {
                    if(fw[i][j] > fw[i][m] + fw[m][j])
                    {
                        fw[i][j] = fw[i][m] + fw[m][j];
                        fw[j][i] = fw[i][m] + fw[m][j];
                    }                        
                }
            }
        }
       
        int answer = Integer.MAX_VALUE;  // 초기값 변경
        for(int i = 1; i <= n; ++i)
        {
            answer = Math.min(answer, fw[s][i] + fw[i][a] + fw[i][b]);
        } 
        
        return answer;
    }
}