# 2093. Minimum Cost to Reach City With Discounts
###### tags: `Leetcode` `Medium` `Dijkstra`
Link: https://leetcode.com/problems/minimum-cost-to-reach-city-with-discounts/description/
## 思路
2D dijkstra
## Code

class Solution {
    public int minimumCost(int n, int[][] highways, int discounts) {
        List<List<int[]>> graph = new ArrayList<>();
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int[] highway: highways){
            int u = highway[0], v = highway[1], w = highway[2];
            graph.get(u).add(new int[]{v, w});
            graph.get(v).add(new int[]{u, w});
        }

        // 0 weight 1 index 2 discount
        Queue<int[]> pq = new PriorityQueue<>((a,b)->(a[0]-b[0]));
        pq.add(new int[]{0,0,0});
        int[][] dist = new int[n][discounts+1];
        for (int i = 0; i < n; i++) Arrays.fill(dist[i], Integer.MAX_VALUE);
        dist[0][0] = 0;

        while(!pq.isEmpty()){
            int[] cur = pq.poll();
            int  cost = cur[0], city = cur[1], dis = cur[2];
            if(city == n-1) return cost;

            for(int[] next:graph.get(city)){
                int nextCity = next[0], nextWeight = next[1];
                if(cost+nextWeight < dist[nextCity][dis]){
                    pq.add(new int[]{cost+nextWeight, nextCity, dis});
                    dist[nextCity][dis] = cost+nextWeight;
                }
                if(dis<discounts && cost+nextWeight/2<dist[nextCity][dis+1]){
                    pq.add(new int[]{cost+nextWeight/2, nextCity, dis+1});
                    dist[nextCity][dis+1] = cost+nextWeight/2;
                }
            }
        }
        
        return -1;
    }
}