fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 1e9 + 7;
  8.  
  9. void countOptimalPaths(int n, vector<vector<int>>& adj, vector<int>& val) {
  10.     vector<int> dist(n + 1, -1);
  11.     vector<int> max_fives(n + 1, 0);
  12.     vector<int> ways(n + 1, 0);
  13.  
  14.     queue<int> q;
  15.  
  16.     // Base Case for Node 1
  17.     dist[1] = 0;
  18.     max_fives[1] = (val[1] == 5 ? 1 : 0);
  19.     ways[1] = 1;
  20.     q.push(1);
  21.  
  22.     while (!q.empty()) {
  23.         int u = q.front();
  24.         q.pop();
  25.  
  26.         for (int v : adj[u]) {
  27.             int is_five = (val[v] == 5 ? 1 : 0);
  28.             int new_fives = max_fives[u] + is_five;
  29.  
  30.             // 1. First time visiting 'v' (guaranteed shortest path)
  31.             if (dist[v] == -1) {
  32.                 dist[v] = dist[u] + 1;
  33.                 max_fives[v] = new_fives;
  34.                 ways[v] = ways[u];
  35.                 q.push(v);
  36.             } 
  37.             // 2. Found an alternative shortest path to 'v'
  38.             else if (dist[v] == dist[u] + 1) {
  39.  
  40.                 // Case A: This path has STRICTLY MORE 5s
  41.                 if (new_fives > max_fives[v]) {
  42.                     max_fives[v] = new_fives;
  43.                     ways[v] = ways[u]; // Reset ways (previous paths were suboptimal)
  44.                 } 
  45.                 // Case B: This path has the EXACT SAME maximum 5s
  46.                 else if (new_fives == max_fives[v]) {
  47.                     ways[v] = (ways[v] + ways[u]) % MOD; // Accumulate ways
  48.                 }
  49.  
  50.                 // Case C: new_fives < max_fives[v]
  51.                 // We do nothing, because this path has fewer 5s than our current best
  52.             }
  53.         }
  54.     }
  55.  
  56.     // Output the results
  57.     for (int i = 1; i <= n; i++) {
  58.         if (dist[i] != -1) {
  59.             cout << "Node " << i << " -> Shortest Path length: " << dist[i] 
  60.                  << ", Max 5s: " << max_fives[i] 
  61.                  << ", Number of such optimal paths: " << ways[i] << "\n";
  62.         } else {
  63.             cout << "Node " << i << " -> Unreachable\n";
  64.         }
  65.     }
  66. }
  67. int main(){}
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/J5RaS8
bfs 3
language:
C++ (gcc 8.3)
created:
2 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!