fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef vector<int> vi;
  6. typedef vector<ll> vl;
  7.  
  8. #define pb push_back
  9. #define endl '\n'
  10. #define INF (long long)1e15
  11. #define EPS 1e-9
  12.  
  13. ll n, m, k;
  14. vector<pair<pair<ll,ll>, ll> >adj[100010];
  15.  
  16. ll dist[300010], from[300010];
  17.  
  18. void dijkstra(){
  19. 	for(ll i = 1; i <= n; i++){
  20. 		dist[i] = INF;
  21. 		from[i] = 0;
  22. 	}
  23. 	priority_queue< pair<ll,ll>, vector<pair<ll,ll> >, greater<pair<ll,ll> > >pq;
  24. 	dist[1] = 0;
  25. 	pq.push(make_pair(0, 1) );
  26. 	while(!pq.empty()){
  27. 		ll cur = pq.top().second;
  28. 		pq.pop();
  29. 		for(int i = 0; i < adj[cur].size(); i++){
  30. 			ll next = adj[cur][i].second;
  31. 			ll w = adj[cur][i].first.first;
  32. 			if( (dist[next] > dist[cur]+w) ){
  33. 				dist[next] = dist[cur]+w;
  34. 				from[next] = adj[cur][i].first.second;
  35. 				pq.push( make_pair(dist[next], next) );
  36. 			}
  37. 			else if(dist[next] == dist[cur]+w){
  38. 				if(adj[cur][i].first.second == 0){
  39. 					from[next] = 0;
  40. 				}
  41. 			}
  42. 		}
  43. 	}
  44. }
  45.  
  46. int main(){
  47.     ios_base::sync_with_stdio(false);
  48.     cin.tie(NULL);
  49. 	cin >> n >> m >> k;
  50. 	ll a, b, w;
  51. 	for(ll i = 0; i < m; i++){
  52. 		cin >> a >> b >> w;
  53. 		adj[a].push_back(make_pair(make_pair(w, 0), b));
  54. 		adj[b].push_back(make_pair(make_pair(w, 0), a));
  55. 	}
  56. 	for(ll i = 0; i < k; i++){
  57. 		cin >> a >> w;
  58. 		adj[1].push_back(make_pair(make_pair(w, 1), a));
  59. 	}
  60. 	dijkstra();
  61. 	ll ans = k;
  62. 	for(ll i = 1; i <= n; i++){
  63. 		ans -= from[i];
  64. 	}
  65. 	cout << ans;
  66. }
Success #stdin #stdout 0s 6012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0oEi7G
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!