fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define endl '\n'
  4. #define int long long
  5. void solve() {
  6.     int n1,m1;
  7.     cin>>n1>>m1;
  8.     vector<int>A[n1+1];
  9.     int value[n1+1];
  10.     for(int i = 0 ; i<m1 ; i++){
  11.         int a,b;
  12.         cin>>a>>b;
  13.         A[a].push_back(b);
  14.         A[b].push_back(a);
  15.     }
  16.     for(int i = 1 ; i<=n1 ; i++){
  17.         cin>>value[i];
  18.     }
  19.     int d;
  20.     cin>>d;
  21.     queue<int>q;
  22.     int visited[n1+1] = {0},visited2[n1+1] = {0};
  23.     int level[n1+1] = {0},level2[n1+1] = {0};
  24.     int five[n1+1] = {0},five2[n1+1] = {0};
  25.     int ways[n1+1] = {0};
  26.     visited[d] = 1;
  27.     if(value[d]==5){
  28.         five[d] = 1;
  29.     }
  30.     q.push(d);
  31.     while(!q.empty()){
  32.         int node = q.front();
  33.         q.pop();
  34.         for(auto node1 : A[node]){
  35.             if(!visited[node1]){
  36.                 q.push(node1);
  37.                 visited[node1] = 1;
  38.                 level[node1] = level[node]+1;
  39.                 if(value[node1]==5){
  40.                     five[node1] = 1+five[node];
  41.                 }
  42.                 else{
  43.                     five[node1] = five[node];
  44.                 }
  45.             }
  46.             else{
  47.                 if((level[node]+1)==(level[node1])){
  48.                     if(value[node1]==5){
  49.                         five[node1] = max((1+five[node]),five[node1]);
  50.                     }
  51.                     else{
  52.                         five[node1] = max(five[node],five[node1]);
  53.                     }
  54.                 }
  55.             }
  56.         }
  57.     }
  58.     visited2[d] = 1;
  59.     ways[d] = 1;
  60.     q.push(d);
  61.     while(!q.empty()){
  62.         int node = q.front();
  63.         q.pop();
  64.         for(auto node1 : A[node]){
  65.             if(!visited2[node1]){
  66.                 q.push(node1);
  67.                 level2[node1] = level2[node]+1;
  68.                 if(value[node1]==5){
  69.                     five2[node1] = 1+five2[node];
  70.                 }
  71.                 else{
  72.                     five2[node1] = five2[node];
  73.                 }
  74.                 if(five2[node1] == five[node1]){
  75.                     ways[node1] = ways[node];
  76.                 }
  77.                 visited2[node1] = 1;
  78.             }
  79.             else{
  80.                 if((level2[node]+1)==(level2[node1])){
  81.                     if(value[node1]==5){
  82.                         five2[node1] = max((1+five2[node]),five2[node1]);
  83.                     }
  84.                     else{
  85.                         five2[node1] = max(five2[node],five2[node1]);
  86.                     }
  87.                     if(five2[node1]==five[node1]){
  88.                         ways[node1] = ways[node1] + ways[node];
  89.                     }
  90.                 }
  91.             }
  92.         }
  93.     }
  94.     for(int i = 1 ; i<n1+1 ; i++){
  95.         cout<<"No of paths having shortest length from node 1 to node "<<i<<" and maximum no of 5s are : "<<ways[i]<<endl;
  96.     }
  97. }
  98.  
  99. signed main(){
  100.     ios::sync_with_stdio(false); cin.tie(NULL);
  101.     //int t;
  102.     //cin >> t;
  103.     //while(t--){
  104.         solve();
  105.     //}
  106.     return 0;
  107. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6 7
1 2
1 3
2 4
3 4
3 5
4 6
5 6
0 5 5 0 5 0
1
stdout
copy 
No of paths having shortest length from node 1 to node 1 and maximum no of 5s are : 1
No of paths having shortest length from node 1 to node 2 and maximum no of 5s are : 1
No of paths having shortest length from node 1 to node 3 and maximum no of 5s are : 1
No of paths having shortest length from node 1 to node 4 and maximum no of 5s are : 2
No of paths having shortest length from node 1 to node 5 and maximum no of 5s are : 1
No of paths having shortest length from node 1 to node 6 and maximum no of 5s are : 1
https://ideone.com/liO5xN
language:
C++14 (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!