SHARE
TWEET

Untitled

a guest Dec 18th, 2018 158 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  ID: bradyawn
  3.  PROG: contest
  4.  LANG: C++11
  5.  */
  6.  
  7. #include <iostream>
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <fstream>
  11. #include <vector>
  12. #include <deque>
  13. #include <string>
  14. #include <cmath>
  15. #include <map>
  16. #include <unordered_map>
  17. #include <utility>
  18. #include <set>
  19. #include <unordered_set>
  20. #include <ctime>
  21. #include <queue>
  22. #include <stack>
  23. #include <bitset>
  24. #include <random>
  25. #include <cstring>
  26. #include <complex>
  27. #include <cassert>
  28.  
  29. #define fi first
  30. #define se second
  31. #define pb push_back
  32.  
  33. using namespace std;
  34.  
  35. typedef long long ll;
  36. typedef long double ld;
  37. typedef pair<int,int> i2;
  38. typedef pair<ll,ll> ll2;
  39.  
  40. int n, m, k;
  41.  
  42. vector<pair<int, ll>> adj[50001];
  43. ll y[50001]; //yumminess in pasture i
  44.  
  45. ll dist[2][50001]; //[eaten][node]
  46. //ll D[50001]; //[node]
  47. bool ans[50001];
  48.  
  49. struct S
  50. {
  51.     int cur;
  52.     bool eat;
  53.     ll d;
  54.     friend bool operator<(const S &lhs, const S &rhs)
  55.     {
  56.         return lhs.d > rhs.d; //reverse order
  57.     }
  58. };
  59.  
  60. int main()
  61. {
  62.     ifstream inf("dining.in");
  63.     ofstream outf("dining.out");
  64.     outf << setprecision(10);
  65.     ios::sync_with_stdio(0); inf.tie(0);
  66.    
  67.     //    memset(D, -1, sizeof D);
  68.    
  69.     inf >> n >> m >> k;
  70.    
  71.    
  72.     for (int i = 1; i <= n; i++) dist[0][i] = dist[1][i] = 1e18;
  73.    
  74.     while (m--)//NEVER USE M AGAIN
  75.     {
  76.         int a, b, t; inf >> a >> b >> t;
  77.         adj[a].pb({b,t});
  78.         adj[b].pb({a,t});
  79.     }
  80.    
  81.     while (k--)//NEVER USE K AGAIN
  82.     {
  83.         ll a, w;
  84.         inf >> a >> w;
  85.         y[a] = max(y[a], w);
  86.     }
  87.    
  88.     //DONT COMPARE -1 with a numerical value LOL!
  89.     priority_queue<S> pq;
  90.     pq.push({n, 0, 0});
  91.     while (!pq.empty())
  92.     {
  93.         auto node = pq.top(); pq.pop();
  94.         int cur = node.cur;
  95.         ll d = node.d;
  96.         if (d >= dist[node.eat][cur]) continue;
  97.         dist[node.eat][cur] = d;
  98.        
  99.         for (auto e : adj[cur])
  100.             pq.push({e.fi, node.eat, d+e.se});
  101.         if (!node.eat && y[cur] > 0) pq.push({cur, 1, d-y[cur]});
  102.     }
  103.    
  104.     for (int i = 1; i < n; i++)
  105.         outf << (dist[0][i] >= dist[1][i]) << '\n';
  106.    
  107.     return 0;
  108.    
  109. }
  110.  
  111. /*
  112.  Read the problem carefully.
  113.  Don't forget to sort(), mod, ll!!!!
  114.  MULTISET NOT SET
  115.  Initial value = +/- infinity instead of zero!!!
  116.  */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top