fork download 
  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.  
  19. struct Node {
  20. 	int u, i; ll d;
  21. 	bool operator<(const Node& other) const {
  22. 		return d > other.d;  
  23. 	}
  24. }; 
  25.  
  26. int n, m, k, s, t; 
  27. vector<ii> adj[N]; 
  28.  
  29. ll dist[N][6]; // dist[u][i] = Đường đi ngắn nhất từ s đến u và đã sử dụng i vé xe miễn phí
  30.  
  31. ll dijkstra(int s, int t) {
  32. 	for (int u = 1; u <= n; u++) {
  33. 		for (int i = 0; i <= k; i++) dist[u][i] = LINF; 
  34. 	}
  35.  
  36. 	priority_queue<Node> pq; 
  37. 	dist[s][0] = 0;    
  38. 	pq.push({s, 0, dist[s][0]}); 
  39.  
  40. 	while (!pq.empty()) {
  41. 		Node front = pq.top(); pq.pop();  
  42. 		int u = front.u, i = front.i; ll d = front.d;  
  43.  
  44. 		if (d > dist[u][i]) continue;  
  45.  
  46. 		if (u == t) return dist[u][i];   
  47.  
  48. 		for (ii v : adj[u]) {
  49. 			// không sử dụng vé xe miễn phí
  50. 			if (minimize(dist[v.first][i], dist[u][i] + v.second)) {
  51. 				pq.push({v.first, i, dist[v.first][i]});  
  52. 			}
  53.  
  54. 			// sử dụng vé xe miễn phí
  55. 			if (i + 1 <= k) {
  56. 				if (minimize(dist[v.first][i + 1], dist[u][i])) {
  57. 					pq.push({v.first, i + 1, dist[v.first][i + 1]}); 
  58. 				}
  59. 			}
  60. 		}
  61. 	}
  62.  
  63. 	return LINF; 
  64. }
  65.  
  66. int main() {
  67. 	ios::sync_with_stdio(false); 
  68. 	cin.tie(nullptr); 	
  69. 	cin >> n >> m >> k >> s >> t; 
  70.  
  71. 	for (int i = 0; i < m; i++) {
  72. 		int u, v, w; 
  73. 		cin >> u >> v >> w; 
  74. 		adj[u].push_back({v, w}); 
  75. 		adj[v].push_back({u, w}); 
  76. 	}
  77.  
  78. 	ll ans = dijkstra(s, t); 
  79.  
  80. 	cout << ans << '\n';   
  81. }
Success #stdin #stdout 0.01s 7616KB
comments (?)
stdin 
5 6 1 1 5
1 2 10
2 5 10
1 4 3
3 4 5
3 5 3
1 3 20
stdout 
3
https://ideone.com/hGAxbe
language:
C++14 (gcc 8.3)
created:
287 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!