当前位置:首页 » 《资源分享》 » 正文

201912-4 区块链【CCF-CSP真题】_Winnie的博客

22 人参与  2021年10月01日 11:23  分类 : 《资源分享》  评论

点击全文阅读


合理的结构很重要!

遇到时序问题时,可以用小根堆来存事件发生顺序,再一个个弹出执行。
满分代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=510;
vector<int> g[maxn];
vector<vector<int> > l;
vector<int> last[maxn];
int n,m,t,k;
int a,b,c;
struct node
{
	int t,id,fid,hid;//发生时间,当前节点编号,父节点编号,待更新的链标号
	bool operator<(const node&r) const
	{
		return t>r.t;
	}
};
int head[maxn];//每个点的主链是哪条
priority_queue<node> q;//小根堆存待更新的点
void operation()
{
	auto tmp=q.top();
    q.pop();
    int u=tmp.id;
    int fa=tmp.fid;
    int hv=tmp.hid;
    auto &x=l[head[u]],&y=l[hv];
    if(x.size()<y.size()||((x.size()==y.size())&&x.back()>y.back()))
    {
        head[u]=hv;
        for(int i=0;i<g[u].size();i++)
        {
        	int v=g[u][i];
        	if(v!=u&&fa!=v)
        	{
        		q.push({tmp.t+t,v,u,hv});
        	}
	   }
    }    
}
void add(int a,int b)
{
	g[a].push_back(b);
	g[b].push_back(a);
}
int main()
{
	//ios::sync_with_stdio(0);用了此加速就不能用fgets了 
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int a,b; 
		cin>>a>>b;
		add(a,b);
	}
	l.push_back({0});
	cin>>t>>k;
	getchar();
	char str[100];
	while(k--)
	{
	//特殊处理一下未知个数数据
		fgets(str, 100, stdin);
        stringstream ssin(str);
        int in[3], cnt = 0;
        while (ssin >> in[cnt]) cnt ++ ;
        //cout<<cnt<<endl;
        if(cnt==3)
        {   //cout<<"!"<<endl;
        	a=in[0],b=in[1],c=in[2];//点,时间,新块
        	while(q.size()&&q.top().t<=b)//先把该时间之前的全部处理完
        	{
        	    operation();
			}
			l.push_back(l[head[a]]);
			l.back().push_back(c);
			head[a]=l.size()-1;
			for(int i=0;i<g[a].size();i++)
			{
			    int v=g[a][i];
			    if(v!=a)
			    q.push({b+t,v,a,head[a]});
			}
			//q.push({b+t,a});
		}
		if(cnt==2)
		{
			a=in[0],b=in[1];//查询点、时间
			while(q.size()&&q.top().t<=b)//先把该时间之前的全部处理完
        	{
        	    operation();
			}
			cout<<l[head[a]].size()<<' ';
			for(int i=0;i<l[head[a]].size();i++) cout<<l[head[a]][i]<<' ';
			cout<<endl;
		}
	}
	return 0;
}

点击全文阅读


本文链接:http://zhangshiyu.com/post/29096.html

时间  节点  把该  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 桃花依然笑春风全书+后续+结局(陆乘渊云梵音)列表_桃花依然笑春风(陆乘渊云梵音)桃花依然笑春风全书+后续+结局在线
  • 经年离歌愁未休,顾允廷宋卿落结局+番外完结完本_完本经年离歌愁未休,顾允廷宋卿落结局+番外完结
  • 「当了七年舔狗,发现认错人了」后续已完结_「尤曜江月路妤」小说精彩章节分享
  • 经年离歌愁未休完结全书顾允廷宋卿落在线
  • 爱意生根已成恨全(宋云祈)
  • 他站在回忆尽头全书+后续+结局(乔若兮沈辞安)免费_(他站在回忆尽头全书+后续+结局)乔若兮沈辞安列表_笔趣阁(乔若兮沈辞安)
  • 「成全他和养姐后,他却不乐意了」节选免费试读_「裴衍乔乔温霁」节选高光片段速递‌
  • 完结文经年离歌愁未休全书+后续+结局列表_完结文经年离歌愁未休全书+后续+结局(顾允廷宋卿落)
  • (番外)+(全书)顾尘傅雅宁(神女老婆,却在背地承欢作乐+后续+结局)_顾尘傅雅宁免费列表_笔趣阁(神女老婆,却在背地承欢作乐+后续+结局)
  • 霍沉洲沈青禾在线品鉴列表_霍沉洲沈青禾在线品鉴
  • 神女老婆,却在背地承欢作乐+全书+番外(顾尘傅雅宁)列表_神女老婆,却在背地承欢作乐+全书+番外(顾尘傅雅宁)结局篇+番外在线
  • 综武反派我的师娘是黄蓉龙云郭靖+后续+完结_综武反派我的师娘是黄蓉龙云郭靖+后续+完结列表

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1