Shortest Path Revisited

In the country of HackerEarth, there are N cities and M bi - directional roads. We need to transport essential items from City 1  to all other cities. (There exists a path always)

But every road has some positive amount of Toll Charge associated with it say C (it is not same for all roads). We need to find the minimum amount of charge that it required to deliver essential items for each city.

Fortunately, to our rescue we have K special offers, which means while travelling from City 1 to any other city we can select at-most K roads and we will not be charged for using those roads. 

Can you now find the minimum charge that we have to pay to deliver essential items for each city.

(Remember we require to provide answers for each destination city separately i.e. we have K offers for every city and not as a whole)

Example:

Input:
5 6 1
1 2 2
1 3 6
2 4 6
2 5 8
3 5 4
4 5 1
Output:
0 0 0 2 2

Approach

Java

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class ShortestPathRevisited {
    static int cost[][];

    static class pair {
        int to, toll;

        pair(int t, int l) {
            to = t;
            toll = l;
        }

    }

    public static void main(String[] args) {
        int n = 5, m = 6, k = 1;
        LinkedList<pair> l[] = new LinkedList[n + 1];
        for (int i = 0; i <= n; i++)
            l[i] = new LinkedList<pair>();

        int cost[][] = new int[n + 1][k + 1];
        for (int i = 2; i <= n; i++)
            Arrays.fill(cost[i], Integer.MAX_VALUE);

        int arr[][] = { { 1, 2, 2 }, { 1, 3, 6 }, { 2, 4, 6 }, { 2, 5, 8 }, { 3, 5, 4 }, { 4, 5, 1 } };

        for (int i = 0; i < m; i++) {
            int u = arr[i][0], v = arr[i][1], c = arr[i][2];
            l[u].add(new pair(v, c));
            l[v].add(new pair(u, c));
        }

        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);

        while (q.size() != 0) {
            int u = q.poll();
            for (pair v : l[u]) {
                int cst = cost[u][0] + v.toll;
                boolean update = false;
                if (cost[v.to][0] > cst) {
                    cost[v.to][0] = cst;
                    update = true;
                }

                for (int offers = 1; offers <= k; offers++) {
                    int mc = Math.min(cost[u][offers - 1], cost[u][offers] + v.toll);
                    if (cost[v.to][offers] > mc) {
                        cost[v.to][offers] = mc;
                        update = true;
                    }
                }

                if (update == true) {
                    q.add(v.to);
                }
            }

        }

        for (int i = 1; i <= n; i++)
            System.out.print(cost[i][k] + " ");

    }
}