A*算法求K短路模板 POJ 2449

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int maxn=2e6+5;

struct asd{

    int from,to,next,val;

}b[maxn],b2[maxn];

int head[maxn],tot=1;

int h2[maxn],t2=1;

int n,m;

void ad(int aa,int bb,int cc){

    b[tot].from=aa;

    b[tot].to=bb;

    b[tot].val=cc;

    b[tot].next=head[aa];

    head[aa]=tot++;

}

void ad2(int aa,int bb,int cc){

    b2[t2].from=aa;

    b2[t2].to=bb;

    b2[t2].val=cc;

    b2[t2].next=h2[aa];

    h2[aa]=t2++;

}

struct jie{

    int num,dis;

    jie(int aa=0,int bb=0){

        num=aa,dis=bb;

    }

    bool operator < (const jie& A) const{

        return dis>A.dis;

    }

};

priority_queue<jie> q;

int dis[maxn];

bool vis[maxn];

void DIJ(int xx){

    dis[xx]=0;

    q.push(jie(xx,0));

    while(!q.empty()){

        int now=q.top().num;

        q.pop();

        if(vis[now]) continue;

        vis[now]=1;

        for(int i=head[now];i!=-1;i=b[i].next){

            int u=b[i].to;

            if(dis[u]>dis[now]+b[i].val){

                dis[u]=dis[now]+b[i].val;

                q.push(jie(u,dis[u]));

            }

        }

    }

}

struct as{

    int qd,hx,gx;

    as(int aa=0,int bb=0,int cc=0){

        qd=aa,hx=bb,gx=cc;

    }

    bool operator < (const as& A) const{

        return hx+gx>A.hx+A.gx;

    }

};

int cnt[maxn];

priority_queue<as> qq;

int Astar(int s,int t,int k){

    if(dis[s]==0x3f3f3f3f) return -1;

    qq.push(as(s,dis[s],0));

    while(!qq.empty()){

        int nqd=qq.top().qd,nhx=qq.top().hx,ngx=qq.top().gx;

        qq.pop();

        cnt[nqd]++;

        if(cnt[nqd]==k && nqd==t) return ngx;

        if(cnt[nqd]>k) continue;

        for(int i=h2[nqd];i!=-1;i=b2[i].next){

            int u=b2[i].to;

            qq.push(as(u,dis[u],ngx+b2[i].val));

        }

    }

    return -1;

}

int main(){

    memset(dis,0x3f,sizeof(dis));

    memset(head,-1,sizeof(head));

    memset(h2,-1,sizeof(h2));

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;i++){

        int aa,bb,cc;

        scanf("%d%d%d",&aa,&bb,&cc);

        ad2(aa,bb,cc);

        ad(bb,aa,cc);

    }

    int s,t,k;

    scanf("%d%d%d",&s,&t,&k);

    if(s==t) ++k;

    DIJ(t);

    printf("%d\n",Astar(s,t,k));

    return 0;

}
巴特西

A*算法求K短路模板 POJ 2449

最新文章

热门文章
