Challenge: Delivery Distances

Lab Java Intermediate 20 points

A delivery van starts at depot 1. Roads are two-way with lengths. Print the shortest distance from the depot to every place 1 … n, or -1 for places it can't reach. Use Dijkstra.

Input

Line 1: n m. Then m lines u v length (lengths ≥ 0).

Output

n distances separated by spaces.

Example

Input

Output

0 3 1 8 11

Sample input available Sample output available

Editor

Java

Hints

Store roads as {neighbour, length} pairs, both directions.

PriorityQueue of {place, distance}; skip entries whose distance is bigger than dist[place].

Solution explanation

O((n + m) log n). Places never reached keep “infinity” and are printed as −1.

Show solution

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class ByDistance implements Comparator<long[]> {
    public int compare(long[] a, long[] b) { return Long.compare(a[1], b[1]); }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        ArrayList<ArrayList<int[]>> g = new ArrayList<ArrayList<int[]>>();
        for (int i = 0; i <= n; i++) g.add(new ArrayList<int[]>());
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
            g.get(u).add(new int[]{v, w});
            g.get(v).add(new int[]{u, w});
        }
        long[] dist = new long[n + 1];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[1] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<long[]>(new ByDistance());
        pq.offer(new long[]{1, 0});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            int u = (int) top[0];
            if (top[1] > dist[u]) continue;
            for (int[] e : g.get(u)) {
                if (dist[u] + e[1] < dist[e[0]]) {
                    dist[e[0]] = dist[u] + e[1];
                    pq.offer(new long[]{e[0], dist[e[0]]});
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            if (i > 1) sb.append(' ');
            sb.append(dist[i] == Long.MAX_VALUE ? -1 : dist[i]);
        }
        System.out.println(sb);
    }
}

Output

Answer