题解 P3946 【ことりのおやつ(小鸟的点心)】
突然发现没有迪杰斯特拉的算法,于是我写了一个
我的算法核心为在裸的算法中差入:
if (b[x]||l[x]<(h[x]+tim*q1)) continue;
其中,b[x]记录是否访问过该点,tim为到该店的时间(即堆的第一维度取反),q1为雪下的速率,l[x]为该点最大容纳量
这样就能判断雪下过头时不能通过了
AC代码如下:
#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<long,long> >q;//大根堆
long long n,m,s,t,g,q1,x,y,z,cnt,he[100001],to[1000001],len[1000001],ne[1000001],tim,d[100001],i,h[100001],l[100001];
bool b[100001];
int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&s,&t,&g,&q1);
for (i=1;i<=n;i++)
{
scanf("%lld%lld",&h[i],&l[i]);
}
for (i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
cnt++;
ne[cnt]=he[x];
to[cnt]=y;
len[cnt]=z;
he[x]=cnt;
cnt++;
ne[cnt]=he[y];
to[cnt]=x;
len[cnt]=z;
he[y]=cnt;//邻接表
}
for (i=1;i<=n;i++)
{
b[i]=false;
d[i]=1e9;//数组初始化
}
d[s]=0;
q.push(make_pair(0,s));
while (q.size())
{
x=q.top().second;
tim=-q.top().first;//提取到该点的时间
q.pop();
if (b[x]||l[x]<(h[x]+tim*q1)) continue;//判断
b[x]=true;
for (i=he[x];i!=0 ;i=ne[i])
if (d[to[i]]>d[x]+len[i])
{
d[to[i]]=d[x]+len[i];
q.push(make_pair(-d[to[i]],to[i]));
}
}
if (d[t]>g) printf("wtnap wa kotori no oyatsu desu!");
else printf("%lld",d[t]);
return 0;
}
该算法其实和普通的最短路没什么差别,增加了一个tim提取时间,如果最短路不会的话请戳这里