[lv3] 합승 택시 요금

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

 

다익스트라 E번 or 플로이드-와샬로 풀이한다

 

나는 전자고 후자가 좀 더 효율적이다.

 

1. 모든 정점간 최소 비용 갱신 - 다익스트라 E번 (우선순위 큐 구현이나 가지치기를 빼면 시간초과)

 

2. 답 도출

목적지 S에서 도착지 A, B로 가는 문제를

A,B에서 S로 가는 문제로 치환한다.

 

C를 임의의 지점으로 놓고,

A -> C, B -> C, C -> S로 가는 비용을 모두 더해 최소값을 출력한다.

 

 

 

import java.util.*;

class Solution {

    int[][] adj, cost;
    int E, s, a, b, MAX = Integer.MAX_VALUE / 3;

    int solve() {
        int answer = MAX;

        for(int i=0; i<E; i++)
            answer = Math.min(answer, cost[a][i] + cost[b][i] + cost[i][s]);

        return answer;
    }

    public int solution(int n, int s, int a, int b, int[][] fares) {

        E = n;
        adj = new int[E][E];
        cost = new int[E][E];

        this.s = --s;
        this.a = --a;
        this.b = --b;

        for(int i=0; i<E; i++)
            Arrays.fill(adj[i], MAX);

        for(int i=0; i<E; i++)
            Arrays.fill(cost[i], MAX);

        for(int i=0; i<fares.length; i++) {
            int from = fares[i][0] - 1;
            int to = fares[i][1] - 1;
            int cost = fares[i][2];

            adj[from][to] = adj[to][from] = cost;
        }

        for(int i=0; i<E; i++)
            init(i);

        return solve();
    }

    // 다익스트라 E번 반복
    public void init(int st) {

        // 가중치로 비교
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1[1], o2[1]));

        cost[st][st] = 0;
        pq.offer(new int[]{st, 0});

        while(!pq.isEmpty()) {

            int[] info = pq.poll();
            int cur = info[0];
            int val = info[1];

            // 2차원 최단비용 배열 갱신
            for(int to=0; to<E; to++) {

                // 가지치기
                if(cost[st][cur] < val)
                    continue;

                int originCost = cost[st][to];
                int newCost = cost[st][cur] + adj[cur][to];

                if(originCost > newCost) {
                    cost[st][to] = newCost;
                    pq.offer(new int[]{to, newCost});
                }
            }
        }
    }
}