fork download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	public static void main (String[] args) throws java.lang.Exception
  11. 	{
  12. 		// your code goes here
  13.         Scanner scanner = new Scanner(System.in);
  14.  
  15.         int n = scanner.nextInt();
  16.         int m = scanner.nextInt();
  17.  
  18.         List<Integer>[] adj = new ArrayList[n + 1];
  19.         for (int i = 0; i <= n; i++) {
  20.             adj[i] = new ArrayList<>();
  21.         }
  22.  
  23.         int[] nodeValues = new int[n + 1];
  24.  
  25.         for (int i = 1; i <= n; i++) {
  26.             nodeValues[i] = scanner.nextInt();
  27.         }
  28.         for (int i = 0; i < m; i++) {
  29.             int u = scanner.nextInt();
  30.             int v = scanner.nextInt();
  31.             adj[u].add(v);
  32.             adj[v].add(u);
  33.         }
  34.  
  35.         scanner.close();
  36.         solve(n, adj, nodeValues);
  37. 	}
  38.     public static void solve(int n, List<Integer>[] adj, int[] values) {
  39.         int[] dist = new int[n + 1];
  40.         Arrays.fill(dist, -1);
  41.  
  42.         int[] maxFives = new int[n + 1];
  43.  
  44.         Queue<Integer> queue = new LinkedList<>();
  45.  
  46.         dist[1] = 0;
  47.         maxFives[1] = (values[1] == 5) ? 1 : 0;
  48.         queue.add(1);
  49.  
  50.         while (!queue.isEmpty()) {
  51.             int u = queue.poll();
  52.  
  53.             for (int v : adj[u]) {
  54.                 int vFives = (values[v] == 5) ? 1 : 0;
  55.  
  56.                 if (dist[v] == -1) {
  57.                     dist[v] = dist[u] + 1;
  58.                     maxFives[v] = maxFives[u] + vFives;
  59.                     queue.add(v);
  60.                 } 
  61.                 else if (dist[v] == dist[u] + 1) {
  62.                     int newFivesCount = maxFives[u] + vFives;
  63.                     maxFives[v] = Math.max(maxFives[v], newFivesCount);
  64.                 }
  65.             }
  66.         }
  67.  
  68.         System.out.println("Results (Shortest Path Length + Max Fives):");
  69.         for (int i = 1; i <= n; i++) {
  70.             if (dist[i] == -1) {
  71.                 System.out.println("Node " + i + ": Not Reachable");
  72.             } else {
  73.                 int result = dist[i] + maxFives[i];
  74.                 System.out.println("Node " + i + ": " + result + " (dist=" + dist[i] + ", maxFives=" + maxFives[i] + ")");
  75.             }
  76.         }
  77.     }
  78. }
Success #stdin #stdout 0.28s 59052KB
comments (?)
stdin 
6 7
0 0 0 0 5 0
1 2
1 3
2 5
3 5
2 4
5 6
4 6
stdout 
Results (Shortest Path Length + Max Fives):
Node 1: 0 (dist=0, maxFives=0)
Node 2: 1 (dist=1, maxFives=0)
Node 3: 1 (dist=1, maxFives=0)
Node 4: 2 (dist=2, maxFives=0)
Node 5: 3 (dist=2, maxFives=1)
Node 6: 4 (dist=3, maxFives=1)
https://ideone.com/21NL1J
language:
Java (HotSpot 12)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!