fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. int main() {
  5.  
  6. 	int n;
  7. 	cin>>n;
  8. 	int e;
  9. 	cin>>e;
  10.  
  11. 	vector<int> g[n+1];
  12. 	vector<int> val(n+1, 0);
  13.  
  14. 	for(int i=1; i<=n; i++){
  15. 		cin>>val[i];
  16. 	}
  17.  
  18. 	for(int i=1; i<=e; i++){
  19. 		int u,v;
  20. 		cin>>u;
  21. 		cin>>v;
  22. 		g[u].push_back(v);
  23. 		g[v].push_back(u);
  24. 	}
  25.  
  26. 	int source = 1;
  27.  
  28. 	// solution;
  29.  
  30. 	queue<int> q;
  31.  
  32. 	q.push(source);
  33.  
  34. 	vector<int> record (n+1,-1);
  35. 	record[source]=0;
  36.  
  37. 	// cost of traversal minimum
  38. 	vector<int> cost(n+1, 0);
  39. 	cost[source] = val[source];
  40.  
  41. 	// // number of shortes paths:-
  42. 	// vector<int> count(n+1, 0);
  43.  
  44. 	while(!q.empty()){
  45.  
  46. 		int t = q.front();
  47.  
  48. 		q.pop();
  49.  
  50. 		for(auto x: g[t]){
  51.  
  52. 			if(record[x]<0){
  53. 				q.push(x);
  54. 				record[x] = record[t]+1;
  55. 				// count[x]++;
  56.  
  57. 				// cost:
  58. 				cost[x] = val[x] + cost[t];
  59. 			}
  60. 			// same length:-
  61. 			else if(record[x] == record[t]+1){
  62. 				// count[x]++;
  63.  
  64. 				if(cost[x] < val[x]+cost[t]){
  65. 					cost[x] = val[x] + cost[t];
  66. 				}
  67. 			}
  68. 		}
  69.  
  70. 	}
  71.  
  72. 	for(int i=1; i<=n; i++){
  73. 		cout<< cost[i]/5<< " ";
  74. 	}
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
9 10 
0 5 0 5 5 0 5 5 5
1 2
2 3
3 6
1 4
4 5
5 6
1 7
7 8
8 9
9 6
stdout
copy 
0 1 1 1 2 2 1 2 3
https://ideone.com/zXcnZp
language:
C++14 (gcc 8.3)
created:
6 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!