直接模拟
重点还是在题意理解上,题目的意思是每一次出查询操作时,查询时间一定小于前面所有更新操作的时间,也就是说可以一边读入一边处理,而不用先存起来再排序再处理,代码中也没什么优化,直接模拟就可以过
C++ 代码
#include<bits/stdc++.h>
using namespace std;
vector<int> edge[10005],chain[505];
int n,m,t,k; //和题目参数名称对应
int last[505]; //存储每一条主链最后一块的编号
struct update{
int center,u_last,u_time;
vector<int> u_chain;
bool operator < (const update& u) const {return u_time>u.u_time;}
}Update; //存储传播更新信息
priority_queue<update> q;
void checkUp(int time){
while(q.size()){
int q_time=q.top().u_time;
if(q_time>time) break;
int q_node=q.top().center,q_last=q.top().u_last;
vector<int> q_chain=q.top().u_chain;
for(int to:edge[q_node]){
if(chain[to].size()>q_chain.size()) continue;
else if(chain[to].size()<q_chain.size()||(chain[to].size()==q_chain.size()&&last[to]>q_last)){
chain[to]=q_chain; last[to]=q_last;
Update.center=to; Update.u_time=q_time+t; Update.u_chain=q_chain; Update.u_last=q_last;
q.push(Update);
}
}
q.pop();
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){chain[i].push_back(0);} //last数组全局变量已为0
int u,v;
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
if(u==v) continue;
edge[u].push_back(v); edge[v].push_back(u);
}
scanf("%d%d",&t,&k); getchar();
string str;
for(int i=1;i<=k;i++){
getline(cin,str);
int blank1=0,blank2=0; //找到字符串中空格位置 两个空格三个数 一个空格两个数
for(int j=0;j<str.size();j++)
if(str[j]==' '){
if(blank1==0) blank1=j;
else{blank2=j; break;}
}
if(blank1!=0&&blank2!=0){
int a=stoi(str.substr(0,blank1));
int b=stoi(str.substr(blank1+1,blank2-blank1-1));
int c=stoi(str.substr(blank2+1));
checkUp(b); //把之前的传输更新操作全部完成
chain[a].push_back(c); last[a]=c;
Update.center=a; Update.u_time=b+t; Update.u_chain=chain[a]; Update.u_last=last[a];
q.push(Update);
}
else{
int a=stoi(str.substr(0,blank1));
int b=stoi(str.substr(blank1+1));
checkUp(b); //把之前的传输更新操作全部完成
printf("%d ",chain[a].size());
for(int blo:chain[a]) printf("%d ",blo);
printf("\n");
}
}
return 0;
}