题目： 在一个分布式网络中，有n个节点通过m条边相连，节点编号从1至n。每个节点初始化都有一个相同的“创世块”，链长都为1，每个节点在整个过程中都需要维护一条主链，任何操作都只在主链上进行。在整个系统中产生的每个新块都有唯一的整数编号，创始块的编号为0，其余块的编号都为正整数。当某个节点的链更新时，会将它的主链发送给它相邻的节点（邻居）；而当节点收到链时，决定是否更新自己的主链下列情况可能会导致某个节点的链更新： ·某个节点接收到邻居发送过来的链，与当前自己的主链进行比较：如果接收到的链更长，则将其作为自己的主链；如果收到的链长度与自身主链相同，且最后一块编号更小，则将其作为自己的主链 如果接收到的链更短，则直接忽略该链。 ·某个节点产生一个新块，将新块放在主链的尾部。 假设网络带宽足够大，每个节点状态更新后，会立刻将自己的主链同时发送给所有邻居。每个节点在每个时刻总是先接收链，再产生新块（注意这与实际的区块链工作方式不相同），每个节点发送、接收、产生块不消耗时间，只有在网络中传输链会消耗时间。不过因为一些故障，这个网络可能会出现“分区”的情况，即出现多个子网络，不同子网络的节点无法互相收发消息 在计算机中常用逻辑时钟来定义“时刻”，逻辑时钟初始时间为0，以单位1递增。任意节点传输一条链到其邻居所花费的时间相同，都为1。现在已知整个网络的结构以及每个节点产生新块的时间，需要查询特定时刻某个节点的主链。
输入
从标准输入读入数据。 保证题中所有输入均为整数，并且所有整数绝对值不大于10^9。 第一行两个正整数分别为n，m，分别表示网络的n个节点和m条边。 接下来m行，每行2个正整数ui，vi，（1<=i<=m），表示网络中节点ui和节点vi，具有（双向）连接。 接下来一行两个正整数t，k，分别表示每次传输延时，和操作（产生块或查询）的数量。 接下来k行，每行2或3个正整数： 如果是三个数a，b，c，表示节点a在b，时刻产生了一个编号为ci的块。保证bi<=bi+1（1<=i<=k）。 如果是两个数ai，bi，表示查询节点ai处理完bi时刻及以前的所有操作后的主链。保证对于同一时刻，任何查询在输入文件中都出现在当前时刻所有的新块被产生之后。
输出 输出到标准输出。 依次输出若干行，分别对应每一次查询。 每行第一个正整数L表示主链的长度，接下来L个数表示主链每个块的编号。从链头（一定为0）到链尾依次输出。
输入样例1 5 10 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 1 27 1 1 1 2 1 2 3 1 3 4 1 4 5 1 5 1 1 2 1 3 1 4 1 5 1 1 2 2 2 3 2 4 2 5 2 1 10 10 2 11 9 1 11 2 11 3 11 4 11 5 11 1 12 2 12 3 12 4 12 5 12
输出样例1 2 0 1 2 0 2 2 0 3 2 0 4 2 0 5 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 3 0 1 10 4 0 1 10 9 3 0 1 10 3 0 1 10 3 0 1 10 4 0 1 10 9 4 0 1 10 9 4 0 1 10 9 4 0 1 10 9 4 0 1 10 9
样例解释1 网络中的节点与连接关系形成一张完全图。在时刻1时，所有节点都产生一个块，所以查询结果主链长度都为2，主链更新后，将自己的主链发给所有邻居。 因为传输时间为1，所以在时刻2时，所有节点都收到其他节点发来的主链并更新，更新后发送新的主链给邻居。此时查询所有节点，主链都为01。 节点1在时刻10产生了新的块10，并发送给邻居。所有邻居在时刻11时接收到节点1发送的块10，同时，节点2在时刻11产生了新块11，所以，时刻11时的节点2主链长为4，其余节点主链长为3，所有发生更新的节点在时刻11时向邻居发送自己的主链。 所以在时刻12时，所有节点的主链长为4.
输入样例2 15 13 1 2 2 3 3 4 4 5 1 6 6 7 7 8 8 9 1 10 10 11 11 12 12 13 14 15 6 28 1 1 1 1 2 2 1 6 2 7 13 7 9 7 5 7 3 14 8 14 5 14 11 14 9 25 5 25 13 25 9 29 3 5 29 4 13 29 5 1 53 2 59 6 2 59 1 1000 3 1000 8 1000 9 1000 10 1000 13 1000 14 1000 15 1000
输出样例2 3 0 1 2 2 0 1 1 0 1 0 1 0 3 0 1 2 1 0 1 0 3 0 1 2 2 0 1 2 0 1 2 0 1 4 0 1 2 3 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 5 0 1 2 3 6 1 0 1 0
80分代码
#include <iostream> #include <string> #include <sstream> #include <vector> #include <queue> using namespace std; struct up_info { int index; int time; vector<int> nowlist; friend bool operator < (const up_info &a, const up_info &b) { return a.time > b.time; } }; int n, m, k, t; priority_queue<up_info> taskqueue; vector< vector<int> > adj; vector< vector<int> > list; vector< vector<int> > commands; void Exe(vector< vector< int > >x) { for (int i = 0; i < k; i++) { int node_index = x[i][0]; int time = x[i][1]; int time_t = time; while (!taskqueue.empty()&&taskqueue.top().time <= time_t-t ) { up_info z = taskqueue.top(); vector<int> temp_list = z.nowlist; int now_index = z.index; int size_temp = adj[now_index].size(); for (int j = 0; j <size_temp;j++) { int y = adj[now_index][j]; if (list[y].size() < temp_list.size()) { list[y] = temp_list; up_info cur; cur.index = y; cur.nowlist = list[y]; cur.time = z.time + t; taskqueue.push(cur); } else if (list[y].size() == temp_list.size()) { if (temp_list.back() < list[y].back()) { list[y] = temp_list; up_info cur; cur.index = y; cur.nowlist = list[y]; cur.time = z.time+t; taskqueue.push(cur); } } } taskqueue.pop(); } if (x[i].size() == 2) { int size_t = list[node_index].size(); cout << size_t; for (int j = 0; j < size_t; j++) { cout << " " << list[node_index][j]; } cout << endl; } else if (x[i].size() == 3) { int index = x[i][2]; list[node_index].push_back(index); up_info temp; temp.index = node_index; temp.time = time; temp.nowlist = list[node_index]; taskqueue.push(temp); } } } int main() { freopen("in.txt", "r", stdin); cin >> n >> m; adj.resize(1000); list.resize(1000); for (int i = 1; i <= n; i++) { list[i].push_back(0); } for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; adj[u].push_back(v); adj[v].push_back(u); } cin >> t >> k; stringstream ss; string s; getline(cin, s); for (int i = 0; i < k; ++i) { getline(cin, s); ss.clear(); ss << s; int x; vector<int> tempv; while (ss >> x) tempv.push_back(x); commands.push_back(tempv); } Exe(commands); fclose(stdin); }