fork download 
  1. /**
  2.  * created by : Mostafa Wael (Phoenix)
  3.  * problem name : Number of Shortest paths
  4.  */
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7. void make_edge(int &u,int &v,vector<vector<int>>&graph){
  8.     graph[u].push_back(v);
  9.     graph[v].push_back(u);
  10. }
  11. const int mod=1e9+7;
  12. int bfs(int source,int n,vector<vector<int>>& graph){
  13.     vector<int>distance(n,2e9),counter(n,0);
  14.     vector<bool>isVisited(n);
  15.     queue<int>q;
  16.     distance[source]=0;
  17.     counter[source]=1;
  18.     q.push(source);
  19.     while(!q.empty()){
  20.         int u=q.front(); q.pop();
  21.         if(isVisited[u]) continue;
  22.         isVisited[u]=true;
  23.         for(auto v:graph[u])
  24.  
  25.         if(distance[u]+1<distance[v]){
  26.             distance[v]=distance[u]+1;
  27.             counter[v]=counter[u];
  28.             q.push(v);
  29.         }else if(distance[u]+1==distance[v]){ 
  30.             // if i can visit node with the same distance then number of ways should be number of node v and number of node u
  31.             counter[v]=(counter[v]+counter[u])%mod;
  32.             q.push(v);
  33.         }
  34.     }
  35.     return counter[n-1];
  36. }
  37. int main()
  38. {
  39.     ios::sync_with_stdio(0);
  40.     cin.tie(0);
  41.     cout.tie(0);
  42.     /**
  43.      *  using normal bfs but we can use array to keep track number of ways 
  44.      */
  45.     int n,m; cin>>n>>m;
  46.     vector<vector<int>>graph(n);
  47.     while(m--){
  48.         int u,v;
  49.         cin>>u>>v;
  50.         make_edge(--u,--v,graph);
  51.     }
  52.     cout<<bfs(0,n,graph);
  53.     return 0;
  54. }
  55.  
Runtime error #stdin #stdout #stderr 0.01s 5516KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/4hiLZd
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

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!