原題網址：https://www.hackerrank.com/challenges/bfsshortreach

Given an undirected graph consisting of??nodes (labelled 1 to N) where a specific given node??represents the start position and an edge between any two nodes is of length??units in the graph.

It is required to calculate the shortest distance from start position (Node S) to all of the other nodes in the graph.

Note 1:?If a node is unreachable , the distance is assumed as?.?
Note 2:?The length of each edge in the graph is??units.

Input Format

The first line contains?, denoting the number of test cases.?
First line of each test case has two integers?, denoting the number of nodes in the graph and?, denoting the number of edges in the graph.?
The next??lines each consist of two space separated integers?, where??and??denote the two nodes between which the edge exists.?
The last line of a testcase has an integer?, denoting the starting position.

Constraints?
?
?
?

Output Format

For each of??test cases, print a single line consisting of??space-separated integers, denoting the shortest distances of the N-1 nodes from starting position?. This will be done for all nodes same as in the order of input 1 to N.

For unreachable nodes, print?.

Sample Input

2 4 2 1 2 1 3 1 3 1 2 3 2

Sample Output

6 6 -1 -1 6

Explanation

For test cases 1:

The graph given in the test case is shown as :

S denotes the node 1 in the test case and B,C and D denote 2,3 and 4. Since S is the starting node and the shortest distances from it are (1 edge, 1 edge, Infinity) to the nodes B,C and D (2,3 and 4) respectively.

Node D is unreachable, hence -1 is printed (not Infinity).

For test cases 2:?There are only one edge (2, 3) in a graph with 3 nodes, so node 1 is unreachable from node 2, and node 3 has one edge from node 2, each edge has the length of 6 units. So we output -1 6.

方法：Dijkstra算法。

import java.io.*; import java.util.*;public class Solution {private void find(int from, List<Integer> graph[], int[] dists, int dist) {dists[from] = dist;if (graph[from] == null) return;for(int next : graph[from]) {if (dists[next] == -1 || dist + 6 < dists[next]) find(next, graph, dists, dist + 6);}}public static void main(String[] args) {/* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */Solution solution = new Solution();Scanner scanner = new Scanner(System.in);int t = scanner.nextInt();for(int i = 0; i < t; i++) {int n = scanner.nextInt();int m = scanner.nextInt();List<Integer>[] graph = new List[n];for(int j = 0; j < m; j++) {int v1 = scanner.nextInt() - 1;int v2 = scanner.nextInt() - 1;if (graph[v1] == null) graph[v1] = new ArrayList<>();graph[v1].add(v2);if (graph[v2] == null) graph[v2] = new ArrayList<>();graph[v2].add(v1);}int s = scanner.nextInt() - 1;int[] dists = new int[n];Arrays.fill(dists, -1);solution.find(s, graph, dists, 0);int printed = 0;for(int j = 0; j < n; j++) {if (j == s) continue;if (printed ++ > 0) System.out.print(" ");System.out.print(dists[j]);}System.out.println();}} }

總結

以上是生活随笔為你收集整理的HackerRank Breadth First Search: Shortest Reach的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。