CCF 201912-4 区块链（STL模拟）

好难写的一道题，一开始写是每次记录下每个时间的被传输链和新增块，然后每更新一次bfs全图，但是写不对。。。

下面的代码是参考
https://blog.csdn.net/ri*qi/article/details/104155384

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>
#include <array>

using namespace std;

const int maxn = 1005;
vector<vector<int> >G(1005);
vector<vector<int> >ans(1005,{0});
map<int, unordered_map<int, array<vector<int>, 2> > > actions;
int n,m;
int t,k;

bool judge(const vector<int>&a,const vector<int>&b) {
    if(a.size() < b.size()) return true;
    if(a.size() == b.size() && a.back() > b.back()) return true;
    return false;
}

void bfs(int v,int time) {
    for(int i = 0;i < G[v].size();i++) {
        int now = G[v][i];
        auto& chain = actions[time][now][0];
        if((chain.empty() && judge(ans[now],ans[v])) || (!chain.empty() && judge(chain,ans[v])))
            chain = ans[v];
    }
}

void query(int x,int y) {
    for(auto &action : actions) {
        int curTime = action.first;
        if(curTime > y) break;

        for(auto& vertex:action.second) {
            int v = vertex.first;
            auto &chain = vertex.second[0];
            auto &block = vertex.second[1];
            bool canBfs = judge(ans[v],chain) || !block.empty();
            if(judge(ans[v],chain)) ans[v] = chain;
            for(auto b: block) {
                ans[v].push_back(b);
            }
            if(canBfs) {
                bfs(v,curTime + t);
            }
        }
    }
    actions.erase(actions.begin(),actions.upper_bound(y));
    cout << ans[x].size() << ' ';
    for(auto i: ans[x]) {
        cout << i << ' ';
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio();
    cin >> n >> m;
    for(int i = 1;i <= m;i++) {
        int x,y;cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    cin >> t >> k;
    for(int i = 1;i <= k;i++) {
        int x,y,z;cin >> x >> y;
        if(cin.get() == '\n' || cin.eof()) {
            query(x,y);
        }
        else {
            cin >> z;
            actions[y][x][1].push_back(z);
        }
    }
    return 0;
}