[题解] luogu P2483 【模板】k短路([SDOI2010]魔法猪学院)

第一道黑题……(人家LC大佬前年就做出来了…… LCTQL)

原题链接

一、基本思路:

一道第k短路的题目,果断运用A*。

二、具体想法

1、大家也知道,A*这种东西比较特殊,有$$f(x)$$ ($$f(x)<=g(x)$$)这种神奇的东西,总是让人捉摸不透。
而这道题呢,我们可以建反图跑一边最短路(我爱Dijkstra)来预处理f(x)的值

void dij(){
    bool v[5001];
    memset(v,0,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、

  1. 开一个堆(优先队列),将初始状态(0+f(1),1)压进堆中
  2. 弹出堆顶,并向四周扩展,压入(dist+f(x),x)。
  3. 重复 b. 每次到终点时将 能量总量-此次消耗的能量,并将次数++
  4. 当总能量<0时,return,输出答案,
priority_queue<pair<double,int>,vector<pair<double,int> >,greater<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……我们需要去寻找优化。

  1. 当第k条到终点的路已经走完时,我们还需要扩展n吗?肯定不用的,所以我们在n点时可以直接continue
  2. 我们前面已经预处理出从起点到终点的最短路f(1),那么到终点最多只可能有E/f(1)条不同的路,也就是说每个点最多也就走E/f(1)次,所以当一个点走过E/f(1)次后我们也可以continue
  3. 当堆顶这条路中途花费已经大于现在的能量总量时,显然现在堆中所有的路径已经不可走了,所以可以直接return
void bfs(){
    double MX=E/f[1];
    double sum[5001];
    memset(k,0,sizeof(k[1]));
    for(int i=1;i<=n;i++)sum[i]=0.0;
    priority_queue<pair<double,int>,vector<pair<double,int> >,greater<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(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、小提示:

  • 洛谷的第11个数据点似乎是一个hack数据,A*过不了,于是我们面向数据编程了
  • return比continue的速度不知道快了多少倍!!!(我当初在函数内输出答案,TLE,函数外输出,AC)

三、代码

#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,int end,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,0,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;
}
void bfs(){
    double MX=E/f[1];
    double sum[5001];
    memset(k,0,sizeof(k[1]));
    for(int i=1;i<=n;i++)sum[i]=0.0;
    priority_queue<pair<double,int>,vector<pair<double,int> >,greater<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(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("%d\n",k[n]);
    return 0;
}

四、福利

pixiv 69888657

五、尾声

感谢LC大佬

Last modification:March 23rd, 2019 at 02:20 pm

Leave a Comment