ccf csp-201912-4-区块链（双端队列bfs+链表）

参考博客：点这里

对样例1的过程模拟

• 初始状态
  
• 时刻1，每个节点都产生一个块
  
• 时刻2，所有结点接收到邻居发来的主链，更新自己的主链
  
• 时刻10，结点1产生新块10

• 时刻11，所有结点接收到邻居发来的主链，更新自己的主链（时刻11的同时，结点2先接收链，再产生新块9）
  
• 时刻12，所有结点接收到邻居发来的主链，更新自己的主链

代码如下

#include<bits/stdc++.h>
using namespace std;
const int N = 505,M = 30005;
vector<int> g[N];
int t,ans[M];
struct node{
	int len,block;//主链长度，主链中的块 
	node *next;
	node(int len,int block,node *next=NULL):len(len),block(block),next(next){}
}*p[N];
struct emerge{
	int id,time;//节点i，时间点 
	node *lastBlock;//节点i所维护的主链中的最后一块
	emerge(int id,int time,node *lastBlock=NULL):id(id),time(time),lastBlock(lastBlock){} 
};
deque<emerge> q;
void bfs(int end){
	while(!q.empty()&&q.front().time<=end){
		emerge cur = q.front();
		q.pop_front();
		if(cur.lastBlock->len>p[cur.id]->len||
		(cur.lastBlock->len==p[cur.id]->len&&cur.lastBlock->block<p[cur.id]->block)){
			p[cur.id] = cur.lastBlock;
			for(int i = 0; i < g[cur.id].size(); i++){
				q.push_back(emerge(g[cur.id][i],cur.time+t,p[cur.id]));
			}
		}
	}
}
void print(node *nod){
	int L = nod->len;
	printf("%d ", nod->len);
	for(int i = nod->len; i; i--,nod=nod->next) ans[i]=nod->block;
	for(int i = 1; i <= L; i++) printf("%d ",ans[i]);
	printf("\n");
}
int main()
{
	int n,m,u,v,k,x,y,z;
	scanf("%d%d", &n, &m);
	while(m--){
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	//创世块
	for(int i = 1; i <= n; i++) p[i]=new node(1,0); 
	scanf("%d%d", &t, &k);
	while(k--){
		scanf("%d%d", &x, &y);
		char c = getchar();
		if(c != '\n'){
			scanf("%d", &z);
			bfs(y);//先接收链 
			node *tmp = new node(p[x]->len+1,z,p[x]);
			q.push_front(emerge(x,y,tmp));//后产生新块 
		}else{
			bfs(y);
			print(p[x]);
		}
	}
	return 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

输入样例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