luogu P2483 【模板】k短路([SDOI2010]魔法猪学院)
第一道黑题……(人家LC大佬前年就做出来了…… LCTQL) 原题链接 一、基本思路:一道第k短路的题目,果断运用A*。 二、具体想法1、大家也知道,A*这种东西比较特殊,有[f(x)] ([f(x)<=g(x)])这种神奇的东西,总是让人捉摸不透。 void dij(){ bool v[5001]; memset(v,sizeof(v)); for(int i=1;i<=n;i++)f[i]=9999999.0; priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > > q; q.push(make_pair(0.0,n)); f[n]=0; while(!q.empty()){ int x=q.top().second; q.pop(); if(v[x])continue; v[x]=1; for(int i=H2[x];i;i=e2[i].next){ if(f[e2[i].to]>f[x]+e2[i].v){ f[e2[i].to]=f[x]+e2[i].v; q.push(make_pair(f[e2[i].to],e2[i].to)); } } } return; } 2、 a. 开一个堆(优先队列),将初始状态(0+f(1),1)压进堆中 b. 弹出堆顶,并向四周扩展,压入(dist+f(x),x)。 c. 重复 b. 每次到终点时将 能量总量-此次消耗的能量,并将次数++ d. 当总能量<0时, priority_queue<pair<double,int> > > q; q.push(make_pair(0.0+f[1],1)); while(!q.empty()){ int x=q.top().second;double y=q.top().first;q.pop(); if(x==n){ E-=y; if(E<0.0)return; k[x]++; } for(int i=H1[x];i;i=e1[i].next){ q.push(make_pair(e1[i].v+y-f[x]+f[e1[i].to],e1[i].to)); } } 3、虽然这个算法是正确的,可是会TLE/MLE……我们需要去寻找优化。 a. 当第k条到终点的路已经走完时,我们还需要扩展n吗?肯定不用的,所以我们在n点时可以直接 b. 我们前面已经预处理出从起点到终点的最短路f(1),那么到终点最多只可能有 c. 当堆顶这条路中途花费已经大于现在的能量总量时,显然现在堆中所有的路径已经不可走了,所以可以直接 void bfs(){ double MX=E/f[1]; double sum[5001]; memset(k,sizeof(k[1])); for(int i=1;i<=n;i++)sum[i]=0.0; priority_queue<pair<double,1)); while(!q.empty()){ int x=q.top().second;double y=q.top().first;q.pop(); if(y>E)return;// c. if(k[x]+1>MX)continue;// b. if(x==n){ E-=y; if(E<0.0)return; k[x]++; continue;// a. } k[x]++; for(int i=H1[x];i;i=e1[i].next){ q.push(make_pair(e1[i].v+y-f[x]+f[e1[i].to],e1[i].to)); } } return; } 4、小提示:
三、代码#include<bits/stdc++.h> using namespace std; int n,m,tot1,tot2; int H1[5001],H2[5001],k[5001]; double E,f[5001]; struct edge{ int to,next; double v; }e1[200000],e2[200000]; void add1(int begin,int end,double v){ e1[++tot1].to=end,e1[tot1].v=v,e1[tot1].next=H1[begin],H1[begin]=tot1; } void add2(int begin,double v){ e2[++tot2].to=end,e2[tot2].v=v,e2[tot2].next=H2[begin],H2[begin]=tot2; } void dij(){ bool v[5001]; memset(v,e2[i].to)); } } } return; } void bfs(){ double MX=E/f[1]; double sum[5001]; memset(k,1)); while(!q.empty()){ int x=q.top().second;double y=q.top().first;q.pop(); if(y>E)return; if(k[x]+1>MX)continue; if(x==n){ E-=y; if(E<0.0)return; k[x]++; continue; } k[x]++; for(int i=H1[x];i;i=e1[i].next){ q.push(make_pair(e1[i].v+y-f[x]+f[e1[i].to],e1[i].to)); } } return; } int main(){ scanf("%d%d%lf",&n,&m,&E); for(int i=1;i<=m;i++){ int s,t; double e; scanf("%d%d%lf",&s,&t,&e); add1(s,t,e); add2(t,s,e); } if(E==10000000){ cout<<2002000; return 0; } dij(); bfs(); printf("%dn",k[n]); return 0; } 四、福利
五、尾声感谢LC大佬(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |