fork(13) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5. 	int n,m,k;
  6. 	cin>>n>>m>>k;
  7. //cout<<1;
  8. 	vector<vector<pair<int, int>>> adj(n + 1);
  9.  
  10. 	for(int i=0;i<m;i++){
  11. 		int u, v, w;
  12. 		cin>>u>>v>>w;
  13. 		adj[u-1].push_back({v-1, w});
  14. 		adj[v-1].push_back({u-1, w});
  15. 	}
  16.  
  17. 	vector<vector<int>> dp(n + 1, vector<int>(k + 2, INT_MAX));
  18. 	for(int i = 0;i <=k;i++){
  19. 		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
  20. 		pq.push({0, 0});
  21. 		dp[0][i] = 0;
  22. 		while(!pq.empty()){
  23. 			auto tp = pq.top();
  24. 			pq.pop();
  25. 			int u = tp.second;
  26. 			for(auto it : adj[u]){
  27. 				int v = it.first;
  28. 				int w = it.second;
  29. 				if(i > 0){
  30. 					if(dp[v][i] > min(dp[u][i-1] , dp[u][i] + w)){
  31. 						dp[v][i] = min(dp[u][i-1] , dp[u][i] + w);
  32. 						pq.push({dp[v][i], v});
  33. 					}
  34. 				}
  35. 				else{
  36. 					if(dp[v][i] > dp[u][i] + w){
  37. 						dp[v][i] = dp[u][i] + w;
  38. 						pq.push({dp[v][i], v});
  39. 					}
  40. 				}
  41. 			}
  42.  
  43. 		}
  44.  
  45.  
  46. 	}
  47. 	for(int i = 0;i < n;i++){
  48. 		cout<<dp[i][k]<<" ";
  49. 	}
  50. 	cout<<endl;
  51.  
  52. }
Runtime error #stdin #stdout #stderr 0.01s 5376KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/9DKRu7
language:
C++14 (gcc 8.3)
created:
2 years 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!