Language: C++

#include <bits/stdc++.h>
#include "../lib/graph/graph.hpp"

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

struct Order {
  int id, v, t;

  Order() {}

  Order(int id, int v, int t): id(id), v(v), t(t) {}
};

bool operator<(Order o1, Order o2) {
  return o1.t < o2.t;
}

void sch(int n, int m, const Graph<int> &g, vvi &rootrev) {
  assert(SZ(rootrev) >= n);
  vi prev(n, -1), dist(n, INF);
  priority_queue<P, vector<P>, greater<P>> que;
  prev[0] = 0;
  dist[0] = 0;
  que.push({0, 0});
  while(!que.empty()) {
    P now = que.top(); que.pop();
    int cost = now.first, idx = now.second;
    if(dist[idx] < cost) continue;
    for(int i=0;i<SZ(g[idx]);++i) {
      int next = g[idx][i].to, l = g[idx][i].cost;
      if(prev[next] != -1 || dist[next] < dist[idx] + l) continue;
      dist[next] = dist[idx] + l;
      prev[next] = idx;
      que.push({dist[next], next});
    }
  }
  //printv(prev);

  for(int i=1;i<n;++i) {
    int now = i;
    rootrev[i].push_back(now);
    while(prev[now] != now) {
      now = prev[now];
      rootrev[i].push_back(now);
    }
  }
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n, m; cin >> n >> m;
  Graph<int> g(n);
  vvi dist(n, vi(n, INF));
  for(int i=0;i<n;++i) {
    dist[i][i] = 0;
  }
  for(int i=0;i<m;++i) {
    int a, b, d; cin >> a >> b >> d;
    a--; b--;
    g[a].push_back(Edge<int>(a, b, d));
    g[b].push_back(Edge<int>(b, a, d));
    dist[a][b] = d;
    dist[b][a] = d;
  }

  for(int k=0;k<n;++k) {
    for(int i=0;i<n;++i) {
      for(int j=0;j<n;++j) {
        if(dist[i][k] == INF || dist[k][j] == INF) continue;
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
      }
    }
  }

/*   for(int i=0;i<n;++i) {
    cout << i << ":";
    for(int j=0;j<SZ(g[i]);++j) {
      cout << g[i][j].to << " ";
    }
    cout << endl;
  } */

/*   for(int i=0;i<n;++i) {
    printv(dist[i]);
  } */

  vvi root(n), rootrev(n);
  sch(n, m, g, rootrev);
/*   for(int i=0;i<n;++i) {
    printv(root[i]);
  } */
  for(int i=1;i<n;++i) {
    root[i] = rootrev[i];
    reverse(root[i].begin(), root[i].end());
  }

  int tmax; cin >> tmax;
  //cout << tmax << endl;

  vector<Order> orders;
  for(int i=0;i<tmax;++i) {
    int sz; cin >> sz;
    if(sz) {
      int id, v; cin >> id >> v;
      v--;
      orders.push_back(Order(id, v, i));
    }
  }

/*   for(int i=0;i<SZ(orders);++i) {
    cout << orders[i].id << ":" << orders[i].v << ":" << orders[i].t << endl;
  } */

  vector<int> ans;
  int idx = 0;
  int time = 0;
  while(idx < SZ(orders) && time < tmax) {
    Order now = orders[idx];
    int l = dist[0][now.v];
    if(now.t + l > tmax) {
      idx++;
      continue;
    }
    //cout << now.id << ":" << now.v << ":" << now.t << endl;

    while(time < now.t) {
      ans.push_back(-2);
      time++;
    }

    for(int i=1;i<SZ(root[now.v]);++i) {
      for(int j=0;j<dist[root[now.v][i-1]][root[now.v][i]];++j) {
        ans.push_back(root[now.v][i]);
      }
    }

    for(int i=1;i<SZ(rootrev[now.v]);++i) {
      for(int j=0;j<dist[rootrev[now.v][i-1]][rootrev[now.v][i]];++j) {
        ans.push_back(rootrev[now.v][i]);
      }
    }

    time += 2 * dist[0][now.v];
    //cout << time << endl;
    Order tmp(0, 0, time);
    auto it = lower_bound(orders.begin(), orders.end(), tmp);
    idx = distance(orders.begin(), it);
  }

  while(SZ(ans) < tmax) ans.push_back(-2);
  //printv(ans);
  for(int i=0;i<tmax;++i) {
    cout << ans[i] + 1 << endl;
  }
}


Compiler output:
a.cc:2:10: fatal error: ../lib/graph/graph.hpp: No such file or directory
    2 | #include "../lib/graph/graph.hpp"
      |          ^~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.