fork download
copy 
  1. /*Code by HsonW, 11/2 NH-Hue. Just a newbie <3>
  2. /*Toi Yeu Khanh Huyen <3>*/
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5. using int64=long long;
  6. #define ll long long
  7. const int MOD=1e9+7;
  8. const int MAX=3e5+100;
  9. typedef pair<int,int> ii;
  10. vector<vector<pair<int,ll>>> g1(MAX), g2(MAX);
  11. vector<int> c(MAX);
  12. vector<pair<int,ll>> R;
  13. vector<ll> dj(int n, vector<vector<pair<int,ll>>> &g){
  14.     vector<ll>d(n+1,LLONG_MAX);
  15.     d[1]=0;
  16.     priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<>>pq;
  17.     pq.push({0,1});
  18.     while(!pq.empty()){
  19.         auto [du,u]=pq.top(); pq.pop();
  20.         if(du!=d[u]) continue;
  21.         for(auto &e:g[u]){
  22.             int v=e.first; ll w=e.second;
  23.             if(d[v]>du+w){
  24.                 d[v]=du+w;
  25.                 pq.push({d[v],v});
  26.             }
  27.         }
  28.     }
  29.     return d;
  30. }
  31.  
  32. signed main(){
  33.     #define name "K Huyen"
  34.     ios::sync_with_stdio(0);
  35.     cin.tie(NULL);
  36.     if(fopen(name ".inp","r")){
  37.         freopen(name ".inp","r",stdin);
  38.         freopen(name ".out","w",stdout);
  39.     }
  40.     int n,m,k; cin>>n>>m>>k;
  41.     for(int i=0,u,v;i<m;i++){
  42.         ll x; cin>>u>>v>>x;
  43.         g1[u].push_back({v,x}); g1[v].push_back({u,x});
  44.         g2[u].push_back({v,x}); g2[v].push_back({u,x});
  45.     }
  46.     for(int i=0,s;i<k;i++){
  47.         ll y; cin>>s>>y;
  48.         c[s]++;
  49.         g2[1].push_back({s,y}); g2[s].push_back({1,y});
  50.         R.push_back({s,y});
  51.     }
  52.     auto d1=dj(n,g1), d2=dj(n,g2);
  53.     ll ans=0;
  54.     for(int i=2;i<=n;i++){
  55.         if(!c[i]) continue;
  56.         if(d2[i]==d1[i]) ans+=c[i];
  57.         else ans+=c[i]-1;
  58.     }
  59.     cout<<ans;
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 18252KB
comments (?)
stdin
copy 
4 4 2
1 2 1
2 3 2
1 3 3
3 4 4
3 2
2 4
stdout
copy 
1
https://ideone.com/LI3uoa
language:
C++14 (gcc 8.3)
created:
3 days 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!