题解 P4880 【抓住czx】

· · 题解

本题是一个较为复杂的最短路算法

首先吐槽一下描述有误,这道题有自环虽然并无影响

本题相当于单源多目标最短路,算法主体如下:

1、跑一遍最短路算法,算出源点到其他点的距离;

2、对czx的位置进行分析处理

对于最短路,我们可以用迪杰斯特拉或SPFA,不会的话戳这里

而对于位置分析,首先想的是对czx的时间定位(即在哪段时间内在哪点),想到的是用快排:

void qsort(int l,int r)
{
    int mid=ll[(l+r)/2],i=l,j=r;
    while (i<=j)
    {
        while (ll[i]<mid) i++;
        while (ll[j]>mid) j--;
        if (i<=j)
        {
            swap(ll[i],ll[j]);
            swap(dd[i],dd[j]);
            i++;
            j--;
        }
    }
    if (j>l) qsort(l,j);
    if (i<r) qsort(i,r);
}

这样就能让时间有序,其中ll数组记录时间,dd数组记录在哪个点。 (之所以双写是因为有l记录左边界,有d来做最短路)

如果嫌烦或不会可以用stl模板库,即:

struct ss{
    long long dd,ll;//结构体,其中ll,dd如上
}w[100001];
bool cjj(ss a,ss b)
{
    return a.ll<b.ll;//判断大小(不要问我为什么叫cjj)
}
int main()
{
    ……
    sort(w+1,w+t+1,cjj);//排序
    ……
}

综上,代码就出来了:

#include<bits/stdc++.h>
using namespace std;
struct ss{
    long long dd,ll;
}w[100001];
bool cjj(ss a,ss b)
{
    return a.ll<b.ll;
}
priority_queue<pair<long long,long long> >q;
long long t,e,b1,n,m,s,i,cnt,x,y,z,he[1000001],ne[2000001],l[2000001],to[2000001],d[1000001];
bool b[1000001];
int main()
{
    scanf("%lld%lld%lld%lld",&n,&m,&b1,&e);
    for (i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);//邻接表
        cnt++;
        ne[cnt]=he[x];
        to[cnt]=y;
        l[cnt]=z;
        he[x]=cnt;
        cnt++;
        ne[cnt]=he[y];
        to[cnt]=x;
        l[cnt]=z;
        he[y]=cnt;
    }
    for (i=1;i<=n;i++) d[i]=1e9;
        d[b1]=0;
    q.push(make_pair(0,b1));
    while (q.size())
    {
        x=q.top().second;
        q.pop();
        if (b[x]) continue;
        b[x]=true;
        for (i=he[x];i!=0 ;i=ne[i])
            if (d[to[i]]>d[x]+l[i])
            {
                d[to[i]]=d[x]+l[i];
                q.push(make_pair(-d[to[i]],to[i]));//迪杰斯特拉
            }
    }
    w[0].dd=e;
    w[0].ll=0;//因为刚开始也算一条数据
    scanf("%lld",&t);
    for (i=1;i<=t;i++)
        scanf("%lld%lld",&w[i].ll,&w[i].dd);
    sort(w+1,w+t+1,cjj);
    for (i=0;i<t;i++)
        if (d[w[i].dd]<w[i+1].ll)//注意是小于
        {
            printf("%lld",max(d[w[i].dd],w[i].ll));//划重点,因为可以先到然后守株待兔
            return 0;
        }
    printf("%lld",max(d[w[t].dd],w[t].ll));
    return 0;
}

在最后判断时,我只用了“d[w[i].dd]<w[i+1].ll”因为假如它在之前的话也没关系,有输出时的判断,而若有更小,由于已按时间排完序,它肯定在之前结束了,也到不了这儿