fork download
copy 
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<vector>
  5. #include<set>
  6. #include<utility>
  7. #include<cstring>
  8. #include<stack>
  9. #include<queue>
  10. #include<map>
  11. #include<deque>
  12. #include<cmath>
  13. #include<map>
  14. using namespace std;
  15. typedef long long LL;
  16. typedef pair<LL, LL> pii;
  17. typedef pair<LL, pii> edge;
  18.  
  19. #define inf 1000000000000000LL
  20. const int maxn = 100003;
  21. LL n, m, k;
  22. vector<pii> vr[maxn];
  23. vector<LL> v[maxn];
  24. LL dist[maxn][2];
  25. bool used[maxn];
  26.  
  27. void dij(int t) {
  28. 	for (int i = 0; i < maxn; i++) {
  29. 		dist[i][t] = inf;
  30. 	}
  31. 	dist[0][t] = 0;
  32. 	priority_queue<pii, vector<pii>, greater<pii> > pq;
  33. 	pq.push(pii(0, 0));
  34. 	while (pq.size()) {
  35. 		LL cur = pq.top().second;
  36. 		LL dst = pq.top().first;
  37. 		pq.pop();
  38. 		if (dst != dist[cur][t]) continue;
  39. 		for (int i = 0; i < vr[cur].size(); i++) {
  40. 			LL nxt = vr[cur][i].first;
  41. 			LL c = vr[cur][i].second;
  42. 			if (dist[cur][t] + c < dist[nxt][t]) {
  43. 				dist[nxt][t] = dist[cur][t] + c;
  44. 				pq.push(pii(dist[nxt][t], nxt));
  45. 			}
  46. 		}
  47. 	}
  48. }
  49. int main() {
  50. 	scanf("%I64d%I64d%I64d", &n, &m, &k);
  51. 	for (int i = 0; i < m; i++) {
  52. 		LL a, b, d;
  53. 		scanf("%I64d%I64d%I64d", &a, &b, &d);
  54. 		a--; b--;
  55. 		vr[a].push_back(pii(b, d));
  56. 		vr[b].push_back(pii(a, d));
  57. 	}
  58. 	dij(0);
  59. 	for (int i = 0; i < k; i++) {
  60. 		LL a, d;
  61. 		scanf("%I64d%I64d", &a, &d);
  62. 		a--;
  63. 		vr[0].push_back(pii(a, d));
  64. 		vr[a].push_back(pii(0, d));
  65. 		v[a].push_back(d);
  66. 	}
  67. 	dij(1);
  68. 	for (int i = 0; i < n; i++) {
  69. 		if (dist[i][1] < dist[i][0]) {
  70. 			used[i] = true;
  71. 		}
  72. 		else if (dist[i][1] >= dist[i][0]) {
  73. 			used[i] = false;
  74. 		}
  75. 	}
  76.  
  77. 	int ct = 0;
  78. 	for (int i = 1; i < n; i++) {
  79. 		LL d = min(dist[i][1], dist[i][0]);
  80. 		if (used[i]) {
  81. 			for (int j = 0; j < v[i].size(); j++) if (v[i][j] == d) ct++;
  82. 			ct--;
  83. 			for (int j = 0; j < v[i].size(); j++) {
  84. 				if (v[i][j] > d) ct++;
  85. 			}
  86. 		//	cout << ct;
  87. 		}
  88. 		else {
  89. 			for (int j = 0; j < v[i].size(); j++) if (v[i][j] >= d) ct++;
  90. 		//	cout << ct;
  91. 		}
  92. 		//cout << i << ' ' << ct << endl;
  93. 	}
  94. 	cout << ct;
  95. }
  96.  
Success #stdin #stdout 0s 7440KB
comments (?)
stdin
copy 
2 1 3
1 2 2
2 3
2 3
2 2
stdout
copy 
3
https://ideone.com/opD81j
language:
C++14 (gcc 8.3)
created:
9 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!