Language: C++

#include <bits/stdc++.h>
using namespace std;

constexpr int INF = INT_MAX;
constexpr int MAX_T = 10000;
constexpr int ROOT = 0;

int allBestTourLen;
vector<int> allBestTour;

struct Order{
    int id, dst, time;
    Order(){}
    Order(int id, int dst, int time):id(id),dst(dst),time(time){}
};

struct Edge{
    int from, to, d;
    Edge(){}
    Edge(int from, int to, int d):from(from),to(to),d(d){}
};

struct Graph{
    int V;
    vector<vector<Edge> > g;
    vector<vector<int> > dist;
    vector<bool> onTour;
    vector<vector<int> > orderIds;
    array<Order, MAX_T> orderList; 
    queue<int> orderQue;
    void init(int _V){
        V = _V;
        g.resize(V);
        onTour.resize(V);
        orderIds.resize(V);
    }
    void add_edge(int u, int v, int d){
        g[u].push_back(Edge(u,v,d));
        g[v].push_back(Edge(v,u,d));
    }
    void add_order(int id, int dst, int time){
        orderList[id] = Order(id,dst,time);
        orderQue.push(id);
    }
    bool receive_order(){
        if(orderQue.empty()) return false;
        while(!orderQue.empty()){
            int id = orderQue.front();
            int dst = orderList[id].dst;
            orderIds[dst].emplace_back(id);
            orderQue.pop();
        }
        return true;
    }
    int count_order(int v){
        return orderIds[v].size();
    }
    void clear_order(int v){
        orderIds[v].clear();
    }
    void wf(){
        dist.resize(V, vector<int>(V, INF/3));
        for(auto &v : g){
            for(auto &e : v){
                int u = e.from, v = e.to, d = e.d;
                dist[u][v] = d;
                dist[v][u] = d;
            }
        }
        for(int i=0;i<V;i++){
            dist[i][i] = 0;
        }
        for(int k=0;k<V;k++){
            for(int i=0;i<V;i++){
                for(int j=0;j<V;j++){
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
    }
    vector<Edge> operator [](int i) {
        return g[i];
    }
};

struct Vehicle{
    int from, to;
    int cnt;
    bool onNode, onRoot;
    void init(){
        from = ROOT;
        to = -1;
        cnt = 0;
        onNode = true;
        onRoot = true;
    }
    void move(){
        if(cnt > 0){
            cnt--;
            onNode = false;
            onRoot = false;
        }
        if(cnt == 0){
            from = to;
            to = -1;
            onNode = true;
            onRoot = from == ROOT;
        }
    }
};

double randFloat(double r){
    return double(rand())/RAND_MAX*r;
}

int calc_tour_len(const vector<int> &tour, Graph &graph){
    int len = 0, n = tour.size();
    for(int i=0;i<n-1;i++){
        len += graph.dist[tour[i]][tour[i+1]];
    }
    if(n > 0) len += graph.dist[ROOT][tour[0]] + graph.dist[tour[n-1]][ROOT];
    return len;
}

void rev_insert(vector<int> &a, vector<int> &b, int l, int r){
    for(int i=r-1;i>=l;i--){
        a.emplace_back(b[i]);
    }
}

vector<int> build_path(Graph &graph, int maxLoop = 800, bool init = false){
    vector<int> tour;

    if(init){
        // vector<int> ls;
        // for(int i=0;i<graph.V;i++){
        //     if(graph.count_order(i) > 0 && !graph.onTour[i]){
        //         ls.emplace_back(i);
        //     }
        // }

        // tour = {0,0};
        // for(auto x : ls){
        //     int dmin = INF, j = 1;
        //     for(int i=1;i<int(tour.size());i++){
        //         int tmp = graph.dist[tour[i-1]][x] + graph.dist[x][tour[i]] - graph.dist[tour[i-1]][tour[i]];
        //         if(tmp < dmin){
        //             j = i;
        //             dmin = tmp;
        //         }
        //     }
        //     tour.insert(tour.begin()+j,x);
        // }

        tour.push_back(0);
        vector<bool> used(graph.V,false);
        for(int i=0;i<graph.V-1;i++){
            int dmin = INF, k = -1;
            for(int j=1;j<graph.V;j++){
                if(used[j]) continue;
                if(dmin > graph.dist[tour.back()][j]){
                    dmin = graph.dist[tour.back()][j];
                    k = j;
                }
            }
            tour.emplace_back(k);
            used[k] = true;
        }
        tour.emplace_back(0);
    }
    else{
        tour.emplace_back(0);
        for(int i=0;i<graph.V-1;i++){
            if(graph.count_order(allBestTour[i]) > 0 && !graph.onTour[allBestTour[i]]){
                tour.emplace_back(allBestTour[i]);
            }
        }
        tour.emplace_back(0);
    }

    vector<int> besttour = tour;
    int dif = 0, dmin = 0;

    for(int loopCount = 0; loopCount < maxLoop; loopCount++){
        for(int i=0;i<int(tour.size())-2;i++){
            for(int j=i+1;j<int(tour.size())-1;j++){
                int lhs = graph.dist[tour[i]][tour[i+1]] + graph.dist[tour[j]][tour[j+1]];
                int rhs = graph.dist[tour[i]][tour[j]] + graph.dist[tour[i+1]][tour[j+1]];
                if(lhs > rhs || exp(double(lhs-rhs)*1.3) > randFloat(1.0)){
                    dif += rhs-lhs; 
                    reverse(tour.begin()+i+1, tour.begin()+j+1);
                    if(dif < dmin){
                        dmin = dif;
                        besttour = tour;
                    }
                }
            }
        }
    }

    tour = besttour;
    int n = tour.size();
    vector<int> newtour;
    bool update = false;
    int t = -1;
    for(int loopcount = 0; loopcount < 3; loopcount++){
        for(int i=0;i<n-3;i++){
            for(int j=i+1;j<n-2;j++){
                for(int k=j+1;k<n-1;k++){
                    int d[5], mini = 0;
                    d[0] = graph.dist[tour[i]][tour[i+1]] + graph.dist[tour[j]][tour[j+1]] + graph.dist[tour[k]][tour[k+1]];
                    d[1] = graph.dist[tour[i]][tour[k]] + graph.dist[tour[j+1]][tour[i+1]] + graph.dist[tour[k+1]][tour[j]];
                    d[2] = graph.dist[tour[j+1]][tour[i]] + graph.dist[tour[k]][tour[j]] + graph.dist[tour[k+1]][tour[i+1]];
                    d[3] = graph.dist[tour[j]][tour[k+1]] + graph.dist[tour[i]][tour[j+1]] + graph.dist[tour[k]][tour[i+1]];
                    d[4] = graph.dist[tour[i]][tour[j]] + graph.dist[tour[j+1]][tour[k+1]] + graph.dist[tour[k]][tour[i+1]];
                    for(int m = 1; m <= 4; m++){
                        if(d[m] < d[mini]) mini = m;
                    }
                    if(mini == 0) continue;

                    newtour.clear();
                    newtour.insert(newtour.end(),tour.begin(),tour.begin()+i+1);
                    if (mini == 1){
                        rev_insert(newtour,tour,j+1,k+1);
                        newtour.insert(newtour.end(),tour.begin()+i+1,tour.begin()+j+1);
                    } else if (mini == 2){
                        newtour.insert(newtour.end(),tour.begin()+j+1,tour.begin()+k+1);
                        rev_insert(newtour,tour,i+1,j+1);
                    } else if (mini == 3){
                        newtour.insert(newtour.end(),tour.begin()+j+1,tour.begin()+k+1);
                        newtour.insert(newtour.end(),tour.begin()+i+1,tour.begin()+j+1);
                    } else if (mini == 4){
                        rev_insert(newtour,tour,i+1,j+1);
                        rev_insert(newtour,tour,j+1,k+1);
                    }
                    newtour.insert(newtour.end(),tour.begin()+k+1,tour.end());
                    tour = newtour;

                    dif += d[mini] - d[0];
                    if(dif < dmin){
                        dmin = dif;
                        besttour = tour;
                        update = true;
                        t = loopcount;
                    }
                }
            }
        }
    }

    besttour.erase(besttour.begin());
    besttour.pop_back();
    return besttour;
}

vector<int> build_last_path(Graph &graph, int tlim){
    vector<pair<int,int> > ordls;
    for(int i=1;i<graph.V;i++){
        if(graph.count_order(i) > 0){
            ordls.emplace_back(make_pair(graph.count_order(i),i));
        }
    }
    sort(ordls.rbegin(), ordls.rend());

    int t = 0;
    int cnt = 0, bestcnt = 0, besttime = INF;
    vector<int> tour, besttour;
    vector<bool> used(ordls.size());
    tour.emplace_back(ROOT);
    for(int i=0;i<int(ordls.size());i++){
        int id = ordls[i].second;
        int dif = INF, k = -1;
        for(int j=0;j<int(tour.size())-1;j++){
            int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
            if(d < dif){
                dif = d;
                k = j+1;
            }
        }
        if(graph.dist[tour.back()][id] < dif){
            dif = graph.dist[tour.back()][id];
            k = tour.size();
        }
        if(t + dif <= tlim){
            t += dif;
            cnt += ordls[i].first;
            used[i] = true;
            tour.insert(tour.begin() + k, id);
        }
    }
    bestcnt = cnt;
    besttime = t;
    besttour = tour;

    for(int s = 0; s < 12; s++){
        for(int loopCount = 0; loopCount < 1000; loopCount++){
            for(int i=0;i<int(tour.size())-1;i++){
                for(int j=i+1;j<int(tour.size());j++){
                    int lhs = graph.dist[tour[i]][tour[i+1]] + (j+1<tour.size() ? graph.dist[tour[j]][tour[j+1]] : 0);
                    int rhs = graph.dist[tour[i]][tour[j]] + (j+1<tour.size() ? graph.dist[tour[i+1]][tour[j+1]] : 0);
                    if(t + rhs - lhs > tlim) continue;
                    if(lhs > rhs || exp(double(lhs-rhs)*1.3) > randFloat(1.0)){
                        t += rhs-lhs; 
                        reverse(tour.begin()+i+1, tour.begin()+j+1);
                        if(t < besttime){
                            besttime = t;
                            besttour = tour;
                        }
                    }
                }
            }
        }
        for(int i=0;i<ordls.size();i++){
            if(used[i]) continue;
            int id = ordls[i].second;
            int dif = INF, k = -1;
            for(int j=0;j<int(tour.size())-1;j++){
                int d = graph.dist[tour[j]][id] + graph.dist[id][tour[j+1]] - graph.dist[tour[j]][tour[j+1]];
                if(d < dif){
                    dif = d;
                    k = j+1;
                }
            }
            if(graph.dist[tour.back()][id] < dif){
                dif = graph.dist[tour.back()][id];
                k = tour.size();
            }
            if(t + dif <= tlim){
                t += dif;
                cnt += ordls[i].first;
                used[i] = true;
                tour.insert(tour.begin() + k, id);
                if(cnt > bestcnt){
                    besttour = tour;
                    besttime = t;
                    bestcnt = cnt;
                }
            }
        }
    }
    return besttour;
}

int main(void){
    int V, E, Tmax;
    cin >> V >> E;
    Graph graph;
    graph.init(V);
    for(int i=0;i<E;i++){
        int u, v, d;
        cin >> u >> v >> d;
        u--; v--;
        graph.add_edge(u,v,d);
    }
    graph.wf();

    allBestTour = build_path(graph, 3000, true);
    allBestTourLen = 0;
    for(int i=0;i<int(allBestTour.size())-1;i++){
        allBestTourLen += graph.dist[allBestTour[i]][allBestTour[i+1]];
    }
    allBestTourLen += graph.dist[0][allBestTour.front()] + graph.dist[allBestTour.back()][0];

    cin >> Tmax;

    Vehicle vehicle;
    vehicle.init();
    queue<int> tourQue;
    bool flag = false;

    for(int t=0;t<Tmax;t++){
        // 情報の受け取り
        int n;
        cin >> n;
        for(int i=0;i<n;i++){
            int id, dst;
            cin >> id >> dst;
            dst--;
            graph.add_order(id, dst, t);
        }

        if(t == 9200) flag = true;

        bool turnEnd = false;
        if(vehicle.onRoot){
            flag = false;
            if(graph.receive_order()){
                vector<int> nxtTour = build_path(graph);
                int dt = calc_tour_len(nxtTour, graph);
                if(t + dt < Tmax){
                    for(auto &v : nxtTour){
                        tourQue.push(v);
                        graph.onTour[v] = true;
                    }
                }
                else{
                    nxtTour = build_last_path(graph, Tmax - t);
                    while(!tourQue.empty()) tourQue.pop();
                    for(auto v : nxtTour){
                        tourQue.push(v);
                        graph.onTour[v] = true;
                    }
                }
            }
            else{
                cout << -1 << endl;
                turnEnd = true;
            }
        }

        if(!turnEnd){
            if(vehicle.onNode){
                int dst;
                while(!tourQue.empty()){
                    int v = tourQue.front();
                    if(graph.count_order(v) == 0) tourQue.pop();
                    else break;
                }
                if(tourQue.empty() || flag){
                    dst = ROOT;
                }else{
                    dst = tourQue.front();
                }
                for(auto &e : graph[vehicle.from]){
                    if(vehicle.from == e.to) continue;
                    if(graph.dist[vehicle.from][e.to] + graph.dist[e.to][dst] == graph.dist[vehicle.from][dst] && graph.dist[vehicle.from][e.to] == e.d){
                        vehicle.to = e.to;
                        vehicle.cnt = e.d;
                        break;
                    }
                }
            }
            if(vehicle.to != -1) cout << vehicle.to + 1 << endl;
            else cout << -1 << endl;
            vehicle.move();
            if(vehicle.onNode){
                graph.clear_order(vehicle.from);
                graph.onTour[vehicle.from] = false;
            }
        }
    return 0;
}


Compiler output:
a.cc: In function 'int main()':
a.cc:442:2: error: expected '}' at end of input
  442 | }
      |  ^
a.cc:344:15: note: to match this '{'
  344 | int main(void){
      |               ^