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.  
  19. int n, m, k;  
  20. vector<ii> adj[N];
  21. vector<ii> train_routes;  
  22.  
  23. struct Node {
  24. 	int u; ll d; 
  25. 	bool operator<(const Node& other) const {
  26. 		return d > other.d; 
  27. 	}
  28. }; 
  29.  
  30. ll dist[N]; 
  31.  
  32. void dijkstra(int s) {
  33. 	for (int u = 1; u <= n; u++) dist[u] = LINF; 
  34.  
  35. 	priority_queue<Node> pq;  
  36. 	dist[s] = 0;  
  37. 	pq.push({s, dist[s]});  
  38.  
  39. 	while (!pq.empty()) {
  40. 		Node front = pq.top(); pq.pop();  
  41. 		int u = front.u; ll d = front.d;  
  42.  
  43. 		if (d > dist[u]) continue; 
  44.  
  45. 		for (ii v : adj[u]) {
  46. 			if (minimize(dist[v.first], dist[u] + v.second)) {
  47. 				pq.push({v.first, dist[v.first]}); 
  48. 			}
  49. 		}
  50. 	}
  51. }
  52.  
  53. int in_deg[N]; // in_deg[u] = Bậc vào của u trong đồ thị đường đi ngắn nhất
  54.  
  55. int main() {
  56. 	ios::sync_with_stdio(false); 
  57. 	cin.tie(nullptr); 	
  58. 	cin >> n >> m >> k; 
  59.  
  60. 	for (int i = 0; i < m; i++) {
  61. 		int u, v, w; 
  62. 		cin >> u >> v >> w; 
  63. 		adj[u].push_back({v, w}); 
  64. 		adj[v].push_back({u, w}); 
  65. 	}
  66.  
  67. 	for (int i = 0; i < k; i++) {
  68. 		int v, w; 
  69. 		cin >> v >> w; 
  70. 		adj[1].push_back({v, w}); 
  71. 		adj[v].push_back({1, w});  
  72. 		train_routes.push_back({v, w}); 
  73. 	}
  74.  
  75. 	// Build đồ thị đường đi ngắn nhất với s = 1
  76. 	dijkstra(1);
  77.  
  78. 	for (int u = 1; u <= n; u++) {
  79. 		for (ii v : adj[u]) {
  80. 			if (dist[u] + v.second == dist[v.first]) {
  81. 				in_deg[v.first]++; 
  82. 			}
  83. 		}
  84. 	}
  85.  
  86. 	int ans = 0;  
  87. 	for (ii route : train_routes) {
  88. 		int u = route.first, w = route.second;  
  89. 		if (dist[u] != w) {
  90. 			ans++; 
  91. 		}
  92. 		else {
  93. 			if (in_deg[u] > 1) {
  94. 				ans++; 
  95. 				in_deg[u]--; 
  96. 			}
  97. 		}
  98. 	}
  99.  
  100. 	cout << ans << '\n'; 
  101. }
Success #stdin #stdout 0.01s 6644KB
comments (?)
stdin
copy 
5 5 3
1 2 1
2 3 2
1 3 3
3 4 4
1 5 5
3 5
4 5
5 5
stdout
copy 
2
https://ideone.com/qRzQ3b
language:
C++14 (gcc 8.3)
created:
281 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!