Advertisement
MrBlueTuxedoman

Untitled

Feb 12th, 2024
814
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.01 KB | Source Code | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <map>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7. #include <ext/pb_ds/tree_policy.hpp>
  8.  
  9. #define int long long
  10. #define $AzH_TxdmN$ ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
  11.  
  12. #define all(v) v.begin(),v.end()
  13. #define ep(a,b) emplace_back(make_pair(a,b))
  14. #define pii pair<int,int>
  15. #define heap pii,vector<pii>,greater<pii>
  16. using namespace std;
  17. using namespace __gnu_pbds;
  18.  
  19. typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>__indexed_set;
  20. const int N = 1e6+9;
  21. const int MOD = 1e9+7;
  22. const int add = 50000;
  23. int dist[N];
  24. vector<pii>v[N];
  25. map<int,int>cost;
  26.  
  27. int n,m,p;
  28.  
  29. void bfs(int node)
  30. {
  31.     priority_queue<heap>q;
  32.     for (int i = 0; i < N; ++i)
  33.     {
  34.         dist[i] = MOD;
  35.     }
  36.     dist[node] = 0;
  37.     q.push({0LL,node});
  38.     while(!q.empty())
  39.     {
  40.         int w = q.top().first;
  41.         int nod = q.top().second;
  42.         //cerr<<"current node: "<<nod<<"\tweight: "<<w<<'\n';
  43.         q.pop();
  44.         for (auto i : v[nod])
  45.         {
  46.             if (dist[i.first] > dist[nod]+i.second+cost[i.first])
  47.             {
  48.                 dist[i.first] = dist[nod]+i.second+cost[i.first];
  49.                 q.push({dist[i.first],i.first});
  50.             }
  51.         }
  52.     }
  53. }
  54.  
  55. void solve()
  56. {
  57.     cin>>n>>m>>p;
  58.     for (int i = 0,x,y,z; i < m; ++i)
  59.     {
  60.         cin>>x>>y>>z;
  61.         x += add;
  62.         y += add;
  63.         v[x].ep(y,z);
  64.         v[y].ep(x,z);
  65.     }
  66.     for (int i = 0,x,y; i < p; ++i)
  67.     {
  68.         cin>>x>>y;
  69.         x += add;
  70.         cost[x] += y;
  71.     }
  72.     bfs(52077LL);
  73.     if (dist[52024LL] > n)
  74.     {
  75.         cout<<"IOI\n";
  76.     }
  77.     else
  78.     {
  79.         cout<<"NO KAMP\n";
  80.     }
  81.     //cout<<"distances: "<<dist[52077]<<"\n"<<dist[52025]<<'\n'<<dist[52024]<<'\n';
  82. }
  83.  
  84. signed main()
  85. {
  86.     $AzH_TxdmN$
  87.     int t = 1;
  88.     //cin>>t;
  89.     while(t--)
  90.     {
  91.         solve();
  92.     }
  93. }
  94. /*
  95. 10 2 1
  96. 2077 2025 1
  97. 2025 2024 1
  98. 2024 9
  99. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement