fork download 
  1. /*
  2. * Author     : Apu Das Orgho
  3.  * Problem   : The Monster's Dice (Easy Version)
  4.  * Created on: 27-09-2025
  5.  */
  6. #include<bits/stdc++.h>
  7. #define iamspeed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  8. #define endl '\n'
  9. #define ll int
  10. using namespace std;
  11. const int N = 5e6 + 5;
  12. const ll mod = 998244353;
  13. string s, ss;
  14. ll d, x, y, z, cnt, t, tt, cnt2, sum, ans, res, q, n, m, k, i, j;
  15. vector<pair<ll,ll> > graph[N];
  16. ll dijk(int sz, int dest, int src) {
  17.     priority_queue<pair<ll,ll> > pq;
  18.     pq.push({0, src});
  19.     vector<bool> vis(sz + 2, 0);
  20.     while (!pq.empty()) {
  21.         auto [cost,node] = pq.top();
  22.         pq.pop();
  23.         cost *= -1;
  24.         if (node == dest) {
  25.             return cost;
  26.         }
  27.         if (vis[node])continue;
  28.         vis[node] = true;
  29.         for (auto [child,wt]: graph[node]) {
  30.             pq.push({-cost - wt, child});
  31.         }
  32.     }
  33.     return -1;
  34. }
  35.  
  36. int main() {
  37.     iamspeed
  38.     ///freopen("input.txt","r",stdin);
  39.     ///freopen("output.txt","w",stdout);
  40.     cin >> n >> m >> q;
  41.     set<ll> st;
  42.     int id = 1;
  43.     map<ll,ll> mp;
  44.     map<ll, bool> block;
  45.     vector<pair<ll,ll> > pr;
  46.     st.insert(1);
  47.     st.insert(n);
  48.     while (m--) {
  49.         cin >> x >> y >> z;
  50.         st.insert(x);
  51.         st.insert(y);
  52.         pr.push_back({x, y});
  53.     }
  54.     vector<ll> queries(q);
  55.     for (i = 0; i < q; i++) {
  56.         cin >> queries[i];
  57.         st.insert(queries[i]);
  58.     }
  59.     vector<ll> v2;
  60.     copy(st.begin(), st.end(), back_inserter(v2));
  61.     st.clear();
  62.     vector<pair<ll,ll> > v;
  63.     for (ll x: v2) {
  64.         for (i = 0; i <= 6; i++) {
  65.             if (!st.count(x + i) && x + i <= n) {
  66.                 st.insert(x + i);
  67.             }
  68.         }
  69.     }
  70.     for (ll val: st) {
  71.         mp[val] = id++;
  72.     }
  73.     ll sz = id;
  74.     for (auto [val,id]: mp) {
  75.         v.push_back({val, id});
  76.     }
  77.     sort(v.begin(), v.end());
  78.     for (i = 0; i <= id + 5; i++) {
  79.         graph[i].clear();
  80.     }
  81.     for (auto [xx,yy]: pr) {
  82.         xx = mp[xx], yy = mp[yy];
  83.         block[xx] = true;
  84.         graph[xx].push_back({yy, 0});
  85.     }
  86.     for (i = 0; i < v.size(); i++) {
  87.         auto [ai,id] = v[i];
  88.         if (block[id])continue;
  89.         int ct = 0;
  90.         for (j = i + 1; j < v.size(); j++) {
  91.             auto [aj,nid] = v[j];
  92.             ll dist = (aj - ai) / 6 + ((aj - ai) % 6 != 0);
  93.             graph[id].push_back({nid, dist});
  94.             if (aj == v[j - 1].first + 1)ct++;
  95.             else ct = 1;
  96.             if (ct >= 6)break;
  97.         }
  98.     }
  99.     for (int id = 0; id < q; id++) {
  100.         cout << dijk(sz, mp[n], mp[queries[id]]) << endl;
  101.     }
  102.  
  103.     return 0;
  104. }
  105.  
Success #stdin #stdout 0.04s 120700KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/vgEmwD
language:
C++14 (gcc 8.3)
created:
4 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!