fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. template<typename T>
  12. bool minimize(T& a, const T& b) {
  13. 	if (b < a) {a = b; return true;}
  14. 	return false;  
  15. }
  16.  
  17. const int N = 1e5 + 5; 
  18. const int M = 1e5 + 5; 
  19.  
  20. // Đỉnh (ga tàu)
  21. // Cạnh (tuyến đường)
  22. struct Edge {
  23. 	int u, v, t;  
  24. };
  25.  
  26. int n, m, s, t, delta;  
  27. vector<int> adj[N]; // adj[u] = Danh sách những cạnh i kề với đỉnh u 
  28. vector<ii> g[M]; // g[i] = Danh sách những cạnh j kề với cạnh i cùng chi phí thời gian để chuyển tuyến từ i sang j
  29. Edge edges[M]; 
  30.  
  31. struct Node {
  32. 	int i; ll d; 
  33. 	bool operator<(const Node& other) const {
  34. 		return d > other.d; 
  35. 	}
  36. }; 
  37.  
  38. ll dist[M]; // dist[i] = Đường đi ngắn nhất từ s đến cạnh thứ i 
  39.  
  40. void dijkstra(int s) {
  41. 	for (int i = 1; i <= m; i++) dist[i] = LINF;   
  42.  
  43. 	priority_queue<Node> pq; 
  44. 	for (int i : adj[s]) {
  45. 		dist[i] = edges[i].t;
  46. 		pq.push({i, dist[i]});  
  47. 	}
  48.  
  49. 	while (!pq.empty()) {
  50. 		Node front = pq.top(); pq.pop(); 
  51. 		int i = front.i; ll d = front.d;  
  52.  
  53. 		if (d > dist[i]) continue;  
  54.  
  55. 		for (ii j : g[i]) {
  56. 			if (minimize(dist[j.first], dist[i] + j.second + edges[j.first].t)) {
  57. 				pq.push({j.first, dist[j.first]}); 
  58. 			}
  59. 		}
  60. 	}
  61. }
  62.  
  63. int main() {
  64. 	ios::sync_with_stdio(false); 
  65. 	cin.tie(nullptr); 	
  66. 	cin >> n >> m >> s >> t >> delta; 
  67.  
  68. 	for (int i = 1; i <= m; i++) {
  69. 		int u, v, t; 
  70. 		cin >> u >> v >> t; 
  71. 		adj[u].push_back(i); 
  72. 		edges[i] = {u, v, t}; 
  73. 	}
  74.  
  75. 	for (int i = 1; i <= m; i++) {
  76. 		int v = edges[i].v; 
  77. 		for (int j : adj[v]) {
  78. 			int f = i * delta + j;   
  79. 			g[i].push_back({j, f});  
  80. 		}
  81. 	}
  82.  
  83. 	dijkstra(s);  
  84.  
  85. 	ll ans = LINF;  
  86. 	for (int i = 1; i <= m; i++) {
  87. 		int v = edges[i].v; 
  88. 		if (v == t) minimize(ans, dist[i]); 
  89. 	}
  90. 	if (ans == LINF) ans = -1;  
  91.  
  92. 	cout << ans << '\n'; 
  93. }
Success #stdin #stdout 0.01s 8364KB
comments (?)
stdin
copy 
5 8 1 5 1
1 2 12
1 3 13
1 4 14
4 2 14
2 3 12
2 5 12
4 5 15
3 5 16
stdout
copy 
31
https://ideone.com/TDnBFB
language:
C++14 (gcc 8.3)
created:
286 days 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!