自动搬运

查看原文

来自洛谷，原作者为

	CherryPockyOvO 赤い瞳

搬运于2025-08-24 21:31:26，当前版本为作者最后更新于2020-02-18 17:21:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最近一直被机房教练逼着做多项式，被搞自闭，所以做一做水题。

结果也被水题搞自闭了

QAQ

首先先看一段本题我原来的代码

#include<cstdio>
#include<queue>
using namespace std;
int n;
queue<int> q[1000040]; 
bool rs[1040];
int spt[1040];
int f[1040][1040];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&spt[i],&f[i][0]);
		for(int j=1;j<=f[i][0];j++) scanf("%d",&f[i][j]);
	}
	rs[1]=1; 
	q[spt[1]].push(1);
	for(int i=1;n;i++){
		while(!q[i].empty()){
			n-=1;
			int now=q[i].front();
			for(int j=1;j<=f[now][0];j++){
				if(rs[f[now][j]]) continue;
				q[i+spt[f[now][j]]].push(f[now][j]);
				rs[f[now][j]]=1;
			}
			q[i].pop();
		}
		if(n==0){
			printf("%d\n",i);
			break;
		}
	}
	return 0;
}

思路清晰，就是每个时间开个queue存储该时间内到达终点牛的编号。样例更是直接水过去…………

可是一交上去全都MLE了，图片太过残忍，就不放了。

显而易见每个时间开个队列这空间必炸……(蒟蒻的我开始没想到……）

因此我们该如何优化呢，这就是优先队列登场的时候了。

这里用小根堆套个二元组，第一元素存储该编号的奶牛到终点的时间，第二个元素存储该牛的编号。

以后每次把队头取出，将这头牛该通知的牛儿全都扫一遍，没通知过的就让他策牛奔腾，向小根堆里加入一个成员，第一元素为当前时间+该牛跑一圈的时间，第二元素就是该牛的编号。

最后一次要注意，因为就剩最后一头牛，其他牛全跑过了，当最后一头牛跑完的时候，弹出，最后队列为空，输出该牛跑完的时间.

详见代码^-^

#include<cstdio>
#include<queue>
using namespace std;
int n;
bool rs[1040];
int spt[1040];
int f[1040][1040];
priority_queue<pair<int,int> > q; 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&spt[i],&f[i][0]);
		for(int j=1;j<=f[i][0];j++) scanf("%d",&f[i][j]);
	}//读入 
	rs[1]=1;//对第一头牛打标记 
	q.push(make_pair(-spt[1],1));//注意，因为是prioity_queue是大根堆，加入时间的相反数即可实现小根堆 
	while(!q.empty()){
		pair<int,int> now=q.top();
		now.first*=-1; //因为之前加入的是时间的相反数，故要变回来。 
		for(int j=1;j<=f[now.second][0];j++){ //枚举当前牛要通知的所有牛。 
			if(rs[f[now.second][j]]) continue; //如果已经跑过了就不用跑了。 
			q.push(make_pair(-(now.first+spt[f[now.second][j]]),f[now.second][j])); //加入队列，再强调一遍，时间要是相反数！！! 
			rs[f[now.second][j]]=1; //对该牛打上标志，已经跑过. 
		}
		q.pop();
		if(q.empty()) printf("%d\n",now.first); //如果队列为空,则所有牛都跑完了，则输出最后一头牛跑完的时间 
	}
	return 0;
}

写的比较丑，多见谅哈!