fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int mxN = 1e4 + 5;
  4.  
  5. long long dist[mxN][35];
  6. vector<pair<int, int>> g[mxN];
  7.  
  8. int main(){
  9. 	ios_base::sync_with_stdio(false);
  10. 	cin.tie(0);
  11. 	int n, m, t;
  12. 	cin >> n >> m >> t;
  13. 	vector<int> c(n);
  14. 	for(int i = 0; i < n; i++) cin >> c[i];
  15. 	for(int i = 0; i < m; i++){
  16. 		int a, b, d;
  17. 		cin >> a >> b >> d;
  18. 		a--, b--;
  19. 		g[a].push_back({b, d});
  20. 		g[b].push_back({a, d});
  21. 	}
  22. 	for(int i = 0; i < n; i++)
  23. 		for(int j = 0; j <= t; j++)
  24. 			dist[i][j] = 1e18;
  25. 	dist[0][t] = 0LL;
  26. 	set<pair<long long, pair<int, int>>> q;
  27. 	q.insert(make_pair(0LL, make_pair(0, t)));
  28. 	while(!q.empty()){
  29. 		pair<long long, pair<int, int>> cur = *q.begin();
  30. 		q.erase(q.begin());
  31. 		for(int i = cur.second.second; i <= (!c[cur.second.first] ? cur.second.second : t); i++){
  32. 			long long cst = cur.first + (c[cur.second.first] * (i - cur.second.second));
  33. 			for(pair<int, int> x : g[cur.second.first]){
  34. 				if(i >= x.second){
  35. 					if(cst < dist[x.first][i - x.second]){
  36. 						q.erase(make_pair(dist[x.first][i - x.second], make_pair(x.first, i - x.second)));
  37. 						dist[x.first][i - x.second] = cst;
  38. 						q.insert(make_pair(dist[x.first][i - x.second], make_pair(x.first, i - x.second)));
  39. 					}
  40. 				}
  41. 			}
  42. 		}
  43. 	}
  44. 	for(int i = 1; i < n; i++){
  45. 		long long mn = 1e18;
  46. 		for(int j = 0; j <= t; j++) mn = min(mn, dist[i][j]);
  47. 		if(mn == 1e18) mn = -1;
  48. 		cout << mn;
  49. 		if(i == (n - 1)) cout << '\n';
  50. 		else cout << ' ';
  51. 	}
  52. 	return 0;
  53. }
Success #stdin #stdout 0s 4384KB
comments (?)
stdin
copy 
5 5 5
1 4 2 5 0
1 2 3
2 3 2
2 4 2
4 5 1
1 3 1
stdout
copy 
0 0 0 2
https://ideone.com/AYS570
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!