fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. void findShortestPathsAndFives(int n, vector<vector<int>>& adj, vector<int>& val) {
  9.     vector<int> dist(n + 1, -1);
  10.     vector<int> max_fives(n + 1, 0);
  11.  
  12.     queue<int> q;
  13.  
  14.     // Base Case: Start from node 1
  15.     dist[1] = 0;
  16.     max_fives[1] = (val[1] == 5 ? 1 : 0);
  17.     q.push(1);
  18.  
  19.     while (!q.empty()) {
  20.         int u = q.front();
  21.         q.pop();
  22.  
  23.         for (int v : adj[u]) {
  24.             int is_five = (val[v] == 5 ? 1 : 0);
  25.  
  26.             // 1. First time reaching 'v' (unvisited)
  27.             if (dist[v] == -1) {
  28.                 dist[v] = dist[u] + 1;
  29.                 max_fives[v] = max_fives[u] + is_five;
  30.                 q.push(v);
  31.             } 
  32.             // 2. Found an alternative shortest path to 'v'
  33.             else if (dist[v] == dist[u] + 1) {
  34.                 // Maximize the number of 5s on the shortest path
  35.                 max_fives[v] = max(max_fives[v], max_fives[u] + is_five);
  36.             }
  37.         }
  38.     }
  39.  
  40.     // Output the results
  41.     for (int i = 1; i <= n; i++) {
  42.         if (dist[i] != -1) {
  43.             cout << "Node " << i << " -> Shortest Path: " << dist[i] 
  44.                  << ", Max 5s: " << max_fives[i] << "\n";
  45.         } else {
  46.             cout << "Node " << i << " -> Unreachable\n";
  47.         }
  48.     }
  49. }
  50. int main(){}
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WY6xxU
bfs 2
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!