P1882 接力赛跑

· · 题解

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

结果也被水题搞自闭了

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;
}

写的比较丑，多见谅哈!