题解 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”因为假如它在之前的话也没关系,有输出时的判断,而若有更小,由于已按时间排完序,它肯定在之前结束了,也到不了这儿