fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     int n,m;
  6.     cin>>n>>m;
  7.  
  8.     vector<int> value(n);
  9.     for(int i=0;i<n;i++)
  10.         cin>>value[i];
  11.  
  12.     vector<vector<int>> adj(n);
  13.     for(int i=0;i<m;i++){
  14.         int u,v;
  15.         cin>>u>>v;
  16.         u--,v--;
  17.         adj[u].push_back(v);
  18.         adj[v].push_back(u);
  19.     }
  20.  
  21.     vector<int> dist(n,-1),cnt5(n,0);
  22.     queue<int> q;
  23.  
  24.     dist[0]=0;
  25.     cnt5[0]=(value[0]==5);
  26.     q.push(0);
  27.  
  28.     while(!q.empty()){
  29.         int u=q.front();
  30.         q.pop();
  31.  
  32.         for(int v:adj[u]){
  33.             if(dist[v]==-1){
  34.                 dist[v]=dist[u]+1;
  35.                 cnt5[v]=cnt5[u]+(value[v]==5);
  36.                 q.push(v);
  37.             }
  38.             else if(dist[v]==dist[u]+1){
  39.                 cnt5[v]=max(cnt5[v],
  40.                             cnt5[u]+(value[v]==5));
  41.             }
  42.         }
  43.     }
  44.  
  45.     for(int i=0;i<n;i++){
  46.         cout<<dist[i]<<" "<<cnt5[i]<<"\n";
  47.     }
  48.  
  49.     return 0;
  50. }
  51.  
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
8 8
0 5 5 0 0 5 5 5
1 2
2 3
3 4
4 5
1 6
6 7
7 8
8 5
stdout
copy 
0 0
1 1
2 2
3 2
4 3
1 1
2 2
3 3
https://ideone.com/LRBfjj
language:
C++ (gcc 8.3)
created:
15 hours 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!