A*模闆

求第k短路。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
const int INF = +;
int n,m,ts,te,k,tot1,tot2,ru,rv,rw;
int first1[],nxt1[],first2[],nxt2[],dis[];
bool used[];
struct edge
{
    int u,v,w;
}l1[],l2[];
struct st
{
    int num,d;
    bool operator < (st a)const
    {
        return d>a.d;
    }
}p1[];
priority_queue<st>q2;
struct heap
{
    int g,h,num;
    bool operator < (heap a)const
    {
        return (g+h)>(a.g+a.h);
    }
}p2[];
priority_queue<heap>q1;
void build_1(int f,int t,int c)
{
    l1[++tot1]=(edge){f,t,c};
    nxt1[tot1]=first1[f];
    first1[f]=tot1;
}
void build_2(int f,int t,int c)
{
    l2[++tot2]=(edge){f,t,c};
    nxt2[tot2]=first2[f];
    first2[f]=tot2;
}
void geth()
{
    for(int i=;i<=n;i++)
    dis[i]=INF;
    dis[te]=;
    q2.push((st){te,});
    while(!q2.empty())
    {
        st h=q2.top();
        q2.pop();
        if(used[h.num]==)
        continue;
        used[h.num]=;
        for(int i=first2[h.num];i!=-;i=nxt2[i])
        {
            int x=l2[i].v;
            if(dis[x]>dis[h.num]+l2[i].w)
            {
                dis[x]=dis[h.num]+l2[i].w;
                q2.push((st){x,dis[x]});
            }
        }
    }
}
void Astar()
{
    geth();
    q1.push((heap){,dis[ts],ts});
    while(!q1.empty())
    {
        heap h=q1.top();
        q1.pop();
        if(h.num==te)
        {
            tot1++;
            if(tot1>=k)
            {
                printf("%d",h.g);
                return;
            }
        }
        for(int i=first1[h.num];i!=-;i=nxt1[i])
        {
            int x=l1[i].v;
            q1.push((heap){h.g+l1[i].w,dis[x],x});
        }
    }
    printf("-1");
}
int main()
{
    memset(first2,-,sizeof(first2));
    memset(first1,-,sizeof(first1));
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++)
    {
        scanf("%d%d%d",&ru,&rv,&rw);
        build_1(ru,rv,rw);
        build_2(rv,ru,rw);
    }
    scanf("%d%d%d",&ts,&te,&k);
    if(ts==te)
    k++;
    tot1=;
    Astar();
    return ;
}
           

注意估價函數設定，對于求第k短路而言，估價函數的影響使得Dijkstra過程中隻會依次嚴格經過第1,2…k短路上的邊到達終點。

求第k短路也可以使用Dijkstra，第k次找到終點的路徑即為由起點到終點的第k短路。

代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
int n,m,ts,te,k,ru,rv,rw,tot;
int first[],nxt[],cnt[];
bool flag;
ll ans;
struct edge
{
    int u,v,w;
}l[];
struct st
{
    int num;
    ll d;
}p;
bool operator < (st a,st b)
{
    return  a.d>b.d;
}
priority_queue<st>q;
void build(int f,int t,int c)
{
    l[++tot]=(edge){f,t,c};
    nxt[tot]=first[f];
    first[f]=tot;
}
void Dijkstra()
{
    q.push((st){ts,});
    while(!q.empty())
    {
        st h=q.top();
        q.pop();
        if(cnt[h.num]>=k)//十分重要的剪枝
        continue;
        cnt[h.num]++;
        if(h.num==te&&cnt[h.num]==k)
        {
            flag=;
            ans=h.d;
            break;
        }
        for(int i=first[h.num];i!=-;i=nxt[i])
        {
            int x=l[i].v;
            q.push((st){x,h.d+l[i].w});
        }
    }
}
int main()
{
    memset(first,-,sizeof(first));
    scanf("%d%d",&n,&m);
    for(int i=;i<=m;i++)
    {
        scanf("%d%d%d",&ru,&rv,&rw);
        build(ru,rv,rw);
    }
    scanf("%d%d%d",&ts,&te,&k);
    tot=;
    Dijkstra();
    if(flag)
    printf("%I64d",ans);
    else printf("-1");
    return ;
}