fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //variable
  4. #define ld long double
  5. #define ll long long
  6. #define db double
  7. #define ii pair<int,int>
  8. #define f first
  9. #define s second
  10. #define mp make_pair
  11. #define mt make_tuple
  12. //vector
  13. #define pb push_back
  14. #define all(v) v.begin(),v.end()
  15. #define len(a) (int)a.length()
  16. #define sz(a) (int)a.size()
  17. //mask
  18. #define BIT(i) (1LL<<(i))
  19. //better code, debugger
  20. #define watch(n) cerr << #n << ": " << n << endl
  21. #define debug(x) for (auto p: x) cerr<<p<<' ';cerr<<endl
  22. #define forw(i,j,z) for(int i=(int)j;i<=(int)z;i++)
  23. #define ford(i,j,z) for (int i=(int)j;i>=(int)z;i--)
  24. #define fIlE "test."
  25. //auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
  26. //mt19937 RAND(seed);
  27. const int mod = 1e9 + 7;
  28. inline int add(int u,int v){u+=v;if(u>=mod)u-=mod;return u;}
  29. inline int dec(int u,int v){u-=v;if(u<0)u+=mod;return u;}
  30. inline int mul(int u,int v){return (ll)u*v%mod;}
  31. #define tt pair<ll, int>
  32. const ll inf = 1e16;
  33. int n, m, k;
  34. vector<ii> a[50000 + 100];
  35. ll dist[50000 + 100][2];
  36. int yummy[50000 + 100];
  37. void solve()
  38. {
  39.     cin >> n >> m >> k;
  40.     while(m--){
  41.         int u, v, d;
  42.         cin >> u >> v >> d;
  43.         a[u].pb(mp(v, d));
  44.         a[v].pb(mp(u, d));
  45.     }
  46.     while(k--){
  47.         int u;
  48.         cin >> u >> yummy[u];
  49.     }
  50.     priority_queue<tt, vector<tt>, greater<tt> > haha;
  51.     forw(i, 1, n)
  52.         dist[i][0] = dist[i][1] = inf;
  53.     haha.push(mp(dist[n][0] = 0, n));
  54.     while(!haha.empty())
  55.     {
  56.         int u; ll d;
  57.         u = haha.top().s, d = haha.top().f;
  58.         haha.pop();
  59.         if (dist[u][0] < d) continue;
  60.         for (auto [v, e] : a[u])
  61.         {
  62.             if (dist[v][0] > e + d)
  63.             {
  64.                 dist[v][0]= e + d;
  65.                 haha.push(mp(dist[v][0], v));
  66.             }
  67.         }
  68.     }
  69.     forw(i, 1, n) if (yummy[i])
  70.         haha.push(mp(dist[i][1] = -yummy[i] + dist[i][0], i));
  71.     while(!haha.empty())
  72.     {
  73.         int u; ll d;
  74.         u = haha.top().s, d = haha.top().f;
  75.         haha.pop();
  76.         if (dist[u][1] < d) continue;
  77.         for (auto [v, e] : a[u])
  78.         {
  79.             if (dist[v][1] > e + d)
  80.             {
  81.                 dist[v][1] = e + d;
  82.                 haha.push(mp(dist[v][1], v));
  83.             }
  84.         }
  85.     }
  86.     forw(i, 1, n - 1)
  87.         if (dist[i][1] <= dist[i][0])
  88.             cout << 1 << '\n';
  89.         else cout << "0\n";
  90. }
  91. signed main()
  92. {
  93.     ios_base::sync_with_stdio(false);
  94.     cin.tie(0);
  95.     freopen("dining.in", "r", stdin);
  96.     freopen("dining.out", "w", stdout);
  97.     //time_t TIME_TU=clock();
  98.     int t=1;
  99. //    cin>>t;
  100.     while(t--)
  101.         solve();
  102.     //time_t TIME_TV=clock();
  103.     //cerr<<(db)(TIME_TV-TIME_TU)/CLOCKS_PER_SEC<<endl;
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/dtwOSw
language:
C++ (gcc 8.3)
created:
11 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!