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. 	vector<int> nodeVal(n);
  8. 	for(int i=0;i<n;i++){
  9. 		cin>>nodeVal[i];
  10. 	}
  11. 	vector<int> adjList[n];
  12. 	for(int i=0;i<m;i++){
  13. 		int x,y;
  14. 		cin>>x>>y;
  15. 		adjList[x].push_back(y);
  16. 		adjList[y].push_back(x);
  17. 	}
  18.  
  19. 	int source=1;
  20. 	vector<int> visited(n, 0);
  21. 	vector<int> level(n, 0);
  22. 	vector<int> ways(n, 0);
  23. 	vector<int> maxPossibleFives(n, 0);
  24. 	queue<int> q;
  25. 	q.push(source);
  26. 	visited[source]=1;
  27. 	if(nodeVal[source]==5)
  28. 		maxPossibleFives[source]=1;
  29. 	else
  30. 		maxPossibleFives[source]=0;
  31. 	ways[source]=1;
  32. 	while(!q.empty()){
  33. 		int node=q.front();
  34. 		q.pop();
  35. 		visited[node]=1;
  36. 		for(auto adjNode : adjList[node]){
  37. 			int pathFives;
  38. 			if(nodeVal[adjNode] == 5) {
  39. 				pathFives = maxPossibleFives[node] + 1;
  40. 			} 
  41. 			else {
  42. 				pathFives = maxPossibleFives[node];
  43. 			}
  44. 			if(!visited[adjNode]){
  45. 				//first time visit
  46. 				visited[adjNode]=1;
  47. 				maxPossibleFives[adjNode] = pathFives;
  48. 				level[adjNode]=level[node]+1;
  49. 				ways[adjNode]=ways[node];
  50. 				q.push(adjNode);
  51. 			}
  52. 			else{
  53. 				if(level[adjNode]==level[node]+1){
  54. 					//node adjNode is on shortest path
  55. 					// ways[adjNode]=ways[adjNode]+ways[node];
  56. 					if(pathFives > maxPossibleFives[adjNode]){
  57. 						maxPossibleFives[adjNode]=pathFives;
  58. 						ways[adjNode]=ways[node];
  59. 					}
  60. 					else if(pathFives==maxPossibleFives[node]){
  61. 						ways[adjNode]=ways[node]+ways[node];
  62. 					}
  63. 				}
  64. 				else{
  65. 					//node adjNode is not on the shortest path
  66. 					//no need to count
  67. 				}
  68. 			}
  69. 		}
  70. 	}
  71. 	for(int i=0;i<maxPossibleFives.size();i++){
  72. 		cout<<"node "<<i<<" : "<<level[i] + maxPossibleFives[i];
  73. 		cout<<"\n";
  74. 	}
  75. 	return 0;
  76. }
  77.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
5 4
0 5 5 0 5
1 2
1 3
2 4
3 4
stdout
copy 
node 0 : 0
node 1 : 1
node 2 : 3
node 3 : 2
node 4 : 5
https://ideone.com/y1XAdu
language:
C++ (gcc 8.3)
created:
4 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!