백준13308 - 최단경로, Dominance Pruning

import java.util.*;
import java.io.*;

public class 주유소13308 {
    static final long INF = 4000 * 2500 * 2500L + 1;
    //1-based
    static int N,M;
    static long[] price;
    //무방향
    static ArrayList<int[]>[] g;
    static long[] bestMinPrice;
    static long dijkstra(int start){
        // i 도착 기준 지금까지 기록된 상태 중 가장 싼 주유소 가격
        bestMinPrice = new long[N+1];
        Arrays.fill(bestMinPrice, Integer.MAX_VALUE);

        long[][] dist = new long[N+1][N+1];
        for(int i = 1; i<=N; i++)
            Arrays.fill(dist[i], INF);
        dist[start][start] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(a->a[2]));
        // 현재, 최소주유소 인덱스, dist
        pq.add(new long[]{start, start, 0});

        while(!pq.isEmpty()){
            long[] cur = pq.poll();
            int ci = (int) cur[0];
            int minIdx = (int) cur[1];
            long cd = cur[2];

            if(cd != dist[ci][minIdx])
                continue;

            if(bestMinPrice[ci] != Integer.MAX_VALUE
                    && bestMinPrice[ci] < price[minIdx])
                continue;
            bestMinPrice[ci] = price[minIdx];

            for(int[] n : g[ci]){
                int ni = n[0];
                long nw = n[1];
                int nIdx = minIdx;
                // 다음 주유소가 새로운 최소가격 주유소인지 확인
                if(price[ni] < price[minIdx]){
                    nIdx = ni;
                }

                long nextCost = dist[ci][minIdx] + (nw * price[minIdx]);

                if(dist[ni][nIdx] > nextCost){
                    dist[ni][nIdx] = nextCost;
                    pq.add(new long[]{ni, nIdx, nextCost});
                }
            }
        }
        long ans = INF;
        for(int i = 1; i<=N; i++){
            ans = Math.min(ans, dist[N][i]);
        }
        return ans;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        price = new long[N+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1; i<=N; i++){
            price[i] = Integer.parseInt(st.nextToken());
        }
        g = new ArrayList[N+1];
        for(int i = 1; i<=N; i++) {
            g[i] = new ArrayList<>();
        }
        while(M-->0){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            g[u].add(new int[]{v,w});
            g[v].add(new int[]{u,w});
        }
        System.out.println(dijkstra(1));
    }
}

 

정리

주유소와 각 주유소 사이의 거리가 주어졌을때 1부터 N까지의 비용의 최솟값을 구하는 문제

주유소에서 기름을 넣고 가중치를 달려야 하므로 최소값은 가중치 * 직전 주유소 가격임

-> 경로상에서 가장 싼 주유소 하나만 알아보면 될것 같지만

-> 가면서 (시간이 진행됨에 따라) 그 전까지 가장 싼 주유소에서 넣고 

다음으로 발견된 싼 주유소가 있으면 그 가격으로 갱신되기 전까지 넣어야 함.

 

풀이

다익스트라 1번만 돌려주면 되는데 

다음 정점을 방문할 때마다 이게 그 전 주유소보다 싼지를 먼저 판단해야함

-> true : nIdx = ni, false : nIdx = minIdx

nextCost = dist [ ci (직전 위치), minIdx(직전 제일싼 곳) ] + price[ minIdx ] * nextWeight 임

이걸 dist [ ni (다음 위치) ] [ nIdx (다음 위치까지에서 제일 싼 곳) ] 에 갱신함.

 

최적화

다익스트라에서 지배 관계 제거 최적화라는게 있는데 

여기서는 현재까지의 minIdx에 따른 주유소 최소값보다 크면 

굳이 그다음에 연결된 주유소를 볼 필요가 없음. 

-> 해당 문제는 단조성을 띔.

 

따라서 다음 정점들을 보기 전에 

bestMinPrice [ i ] 라는 배열을 둬서 i 정점까지의 최소 주유소 가격을 기록하고 

이게 price[ minIdx (현재 큐에서 나온 최소 주유소 가격 인덱스) ] 보다 크면

볼 필요가 없기 때문이다.