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.         long[] pathCount = new long[n + 1];
  44.  
  45.         Queue<Integer> queue = new LinkedList<>();
  46.         dist[1] = 0;
  47.         maxFives[1] = (values[1] == 5) ? 1 : 0;
  48.         pathCount[1] = 1; 
  49.         queue.add(1);
  50.  
  51.         while (!queue.isEmpty()) {
  52.             int u = queue.poll();
  53.             for (int v : adj[u]) {
  54.                 int vFives = (values[v] == 5) ? 1 : 0;
  55.                 int newFivesCount = maxFives[u] + vFives;
  56.                 if (dist[v] == -1) {
  57.                     dist[v] = dist[u] + 1;
  58.                     maxFives[v] = newFivesCount;
  59.                     pathCount[v] = pathCount[u];
  60.                     queue.add(v);
  61.                 } 
  62.                 else if (dist[v] == dist[u] + 1) {
  63.                     if (newFivesCount > maxFives[v]) {
  64.                         maxFives[v] = newFivesCount;
  65.                         pathCount[v] = pathCount[u];
  66.                     }
  67.                     else if (newFivesCount == maxFives[v]) {
  68.                         pathCount[v] += pathCount[u];
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.  
  74.         System.out.println("--- Results (Number of Shortest Paths + Max Fives) ---");
  75.         for (int i = 1; i <= n; i++) {
  76.             if (dist[i] == -1) {
  77.                 System.out.println("Node " + i + ": Not Reachable");
  78.             } else {
  79.                 long result = pathCount[i] + maxFives[i];
  80.                 System.out.println("Node " + i + ": " + result + " (pathCount=" + pathCount[i] + ", maxFives=" + maxFives[i] + ")");
  81.             }
  82.         }
  83.     }
  84. }
Success #stdin #stdout 0.22s 59112KB
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 (Number of Shortest Paths + Max Fives) ---
Node 1: 1 (pathCount=1, maxFives=0)
Node 2: 1 (pathCount=1, maxFives=0)
Node 3: 1 (pathCount=1, maxFives=0)
Node 4: 1 (pathCount=1, maxFives=0)
Node 5: 3 (pathCount=2, maxFives=1)
Node 6: 3 (pathCount=2, maxFives=1)
https://ideone.com/nIzqfr
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!