Dijkstra: Shortest Reach 2 – ASOCIATIA „INVESTESTE PENTRU VIITORUL TAU” BUZAU

Cerinta completa

Given an undirected graph and a starting node, determine the lengths of the shortest paths from the starting node to all other nodes in the graph. If a node is unreachable, its distance is -1. Nodes will be numbered consecutively from to , and edges will have varying distances or lengths.

For example, consider the following graph of 5 nodes:

Begin	End	Weight
1	2	5
2	3	6
3	4	2
1	3	15

Starting at node , the shortest path to is direct and distance . Going from to , there are two paths: at a distance of or at a distance of . Choose the shortest path, . From to , choose the shortest path through and extend it: for a distance of There is no route to node , so the distance is .

The distances to all nodes in increasing node order, omitting the starting node, are 5 11 13 -1.

Function Description

Complete the shortestReach function in the editor below. It should return an array of integers that represent the shortest distance to each node from the start node in ascending order of node number.

shortestReach has the following parameter(s):

n: the number of nodes in the graph
edges: a 2D array of integers where each consists of three integers that represent the start and end nodes of an edge, followed by its length
s: the start node number

Input Format

The first line contains , the number of test cases.

Each test case is as follows:
– The first line contains two space-separated integers and , the number of nodes and edges in the graph.
– Each of the next lines contains three space-separated integers , , and , the beginning and ending nodes of an edge, and the length of the edge.
– The last line of each test case has an integer , denoting the starting position.

Constraints

If there are edges between the same pair of nodes with different weights, they are to be considered as is, like multiple edges.

Output Format

For each of the test cases, print a single line consisting space separated integers denoting the shortest distance to the nodes from starting position in increasing order of their labels, excluding .

For unreachable nodes, print .

Sample Input

Sample Output

24 3 15

Explanation

The graph given in the test case is shown as :

* The lines are weighted edges where weight denotes the length of the edge.

The shortest paths followed for the three nodes 2, 3 and 4 are as follows :

1/S->2 – Shortest Path Value :

1/S->3 – Shortest Path Value :

1/S->3->4 – Shortest Path Value :

Limbajul de programare folosit: java8

Cod:

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;

class Pair implements Comparable<Pair> {

  public int x;
  public int c;

  Pair(int x, int c) {
    this.x = x;
    this.c = c;
  }

  public int compareTo(Pair b) {
    return (b.c < this.c) ? 1 : -1;
  }
}


public class Solution {

  public static ArrayList<HashMap<Integer, Integer>> adj;
  public static int[] shortestPaths;

  public static void dijkstra(int s) {
    shortestPaths = new int[adj.size()];
    for (int i = 0; i < adj.size(); i++) {
      shortestPaths[i] = Integer.MAX_VALUE;
    }
    shortestPaths[s] = 0;
    boolean[] visited = new boolean[adj.size()];
    PriorityQueue<Pair> queue = new PriorityQueue<>();
    queue.add(new Pair(s, 0));

    while (!queue.isEmpty()) {
      Pair current = queue.poll();
      if (!visited[current.x]) {
        visited[current.x] = true;
        Iterator<Map.Entry<Integer, Integer>> entries = adj.get(current.x).entrySet().iterator();

        while (entries.hasNext()) {
          Map.Entry<Integer, Integer> entry = entries.next();
          if (current.c + entry.getValue() < shortestPaths[entry.getKey()]) {
            shortestPaths[entry.getKey()] = current.c + entry.getValue();
            if (!visited[entry.getKey()]) {
              queue.add(new Pair(entry.getKey(), shortestPaths[entry.getKey()]));
            }
          }
        }
      }
    }
  }

  public static void main(String[] args) {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    try {
      int t = Integer.parseInt(in.readLine());
      for (int i = 0; i < t; i++) {
        String[] stmp = in.readLine().split(" ");
        int n = Integer.parseInt(stmp[0]);
        int m = Integer.parseInt(stmp[1]);

        adj = new ArrayList<HashMap<Integer, Integer>>();
        for (int j = 0; j < n; j++) {
          adj.add(new HashMap<>());
        }

        for (int j = 0; j < m; j++) {
          stmp = in.readLine().split(" ");
          int x = Integer.parseInt(stmp[0]);
          int y = Integer.parseInt(stmp[1]);
          int r = Integer.parseInt(stmp[2]);
          x--;
          y--;

          if (!adj.get(x).containsKey(y) || adj.get(x).get(y) > r) {
            adj.get(x).put(y, r);
          }
          if (!adj.get(y).containsKey(x) || adj.get(y).get(x) > r) {
            adj.get(y).put(x, r);
          }
        }

        int s = Integer.parseInt(in.readLine());
        s--;
        dijkstra(s);
        StringBuilder out = new StringBuilder("");
        for (int j = 0; j < n; j++) {
          if (s != j) {
            if (shortestPaths[j] == Integer.MAX_VALUE) {
              out.append("-1 ");
            } else {
              out.append(shortestPaths[j]);
              out.append(" ");
            }
          }
        }
        out.append("\n");
        System.out.print(out.toString());
      }
    } catch (Exception e) {
    }
  }
}

Scor obtinut: 1.0

Submission ID: 464604312

Link challenge: https://www.hackerrank.com/challenges/dijkstrashortreach/problem

Dijkstra: Shortest Reach 2