fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. const int MOD = 1e9 + 7;
  8.  
  9. void countShortestPaths(int n, vector<vector<int>>& adj) {
  10.     // Initialize dist with -1 (unvisited)
  11.     vector<int> dist(n + 1, -1);
  12.     vector<int> ways(n + 1, 0);
  13.  
  14.     queue<int> q;
  15.  
  16.     // Start from node 1
  17.     dist[1] = 0;
  18.     ways[1] = 1;
  19.     q.push(1);
  20.  
  21.     while (!q.empty()) {
  22.         int u = q.front();
  23.         q.pop();
  24.  
  25.         for (int v : adj[u]) {
  26.             // 1. First time reaching 'v' (unvisited)
  27.             if (dist[v] == -1) {
  28.                 dist[v] = dist[u] + 1;
  29.                 ways[v] = ways[u];
  30.                 q.push(v);
  31.             } 
  32.             // 2. Found another shortest path to 'v'
  33.             else if (dist[v] == dist[u] + 1) {
  34.                 ways[v] = (ways[v] + ways[u]) % MOD;
  35.             }
  36.         }
  37.     }
  38.  
  39.     // Output the number of ways to reach each node
  40.     for (int i = 1; i <= n; i++) {
  41.         cout << "Node " << i << ": " << ways[i] << " ways\n";
  42.     }
  43. }
  44. int main(){}
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/sVF0yM
bfs 1
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!