合理的結構很重要！
遇到時序問題時，可以用小根堆來存事件發生順序，再一個個彈出執行，
滿分代碼
#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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/299399.html
標籤：區塊鏈
上一篇：警惕！CHNG仿盤出現！
下一篇：海龜交易法則