fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     int n;
  6.     cin>>n;
  7.     int e;
  8.     cin>>e;
  9.     vector<int>H[n+1];
  10.     for(int i=0;i<e;i++){
  11.     	int c,d;
  12.     	cin>>c>>d;
  13.     	H[c].push_back(d);
  14.     	H[d].push_back(c);
  15.     }
  16.     int nodeVal[n+1]={0};
  17.     for(int i=1;i<=n;i++){
  18.     	cin>>nodeVal[i];  //asssign value for each node either 5 or 0;
  19.     }
  20.     int used[n+1]={0};  //observed or unobserved neighbour
  21.     int level[n+1]={0}; //shortest distance from the source node
  22.     int sPath[n+1]={0}; //number of shortest path
  23.     int no5[n+1]={0};   //number of 5 till the each node
  24.     queue<int>Q;
  25.     int source=1;
  26.     used[source]=1;
  27.     level[source]=0;
  28.     sPath[source]=1;
  29.     if(nodeVal[1]==5){
  30.     	no5[1]=1;
  31.     }
  32.  
  33.  
  34.     Q.push(source);
  35.     while(!Q.empty()){
  36.     	int node=Q.front();
  37.     	// cout<<node<<" ";
  38.     	Q.pop();
  39.     	for(auto c:H[node]){
  40.     		if(nodeVal[c]==5){
  41.     			no5[c]=1;
  42.     		}
  43.     		if(used[c]==0){
  44.     			used[c]=1;
  45.     			level[c]=level[node]+1;
  46.     			Q.push(c);
  47.     			sPath[c]=sPath[node];
  48.     			no5[c]=no5[c]+no5[node];
  49.     		}
  50.     		else{
  51.     			if(level[c]==level[node]+1){
  52.     				sPath[c]=sPath[node]+sPath[c];
  53.     				no5[c]=max(no5[c],no5[c]+no5[node]);
  54.  
  55.  
  56.     			}
  57.     		}
  58.  
  59.     	}
  60.  
  61.     }
  62.     cout<<" shortest path along with maximum number of 5"<<endl;
  63.     for(int i=1;i<=n;i++){
  64.     	cout<<i<<"-"<<level[i]<<" "<<no5[i]<<endl;
  65.     }
  66. 	return 0;
  67. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin 
5 4
1 2
1 3
2 4
3 5
0 5 0 5 5
stdout 
 shortest path along with maximum number of 5
1-0 0
2-1 1
3-1 0
4-2 2
5-2 1
https://ideone.com/yZ0j0Z
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!