k短路

问题模型

给定一个有\(n\)个结点， \(m\)条边的有向图，求从\(s\)到\(t\)的所有不同路径中的第\(k\)短路径的长度。

算法分析

\(A*\)算法\(+Dijkstra\)

先以\(t\)为源点跑一边\(Dijkstra\)，困难的地方其实是在\(A\)_\(star()\)函数的理解，见一下注释：

struct node
{
    int id,g,f;
//g为目前的点到源点的距离，f是一个估计函数（简而言之就是一个估计值）
    bool operator < (node tmp) const
    {
        if(f==tmp.f) return g>tmp.g;
        return f>tmp.f;
    }
};
priority_queue<node> q;
int cnt[N];//计数器优化
void A_star()
{
    if(s==t) ++k;
    q.push((node){s,0,d[s]});
    int nw,dis;
    while(!q.empty())
    {
        nw=q.top().id,
        dis=q.top().g;
        q.pop();
        ++cnt[nw];
        if(cnt[nw]>k) continue;//只需扩展前k小的
        if(nw==t)
        {
            if(cnt[t]==k)
            {
                printf("%d\n",dis);
                return;
            }
        }
        for(int i=h2[nw];i;i=e[i].nx)
            q.push((node){e[i].v,dis+e[i].w,dis+e[i].w+d[e[i].v]});
    }
    puts("-1");
}

例题[POJ2449] Remmarguts' Date代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

const int N=1500,M=250000;
int n,m,s,t,k;
struct edge
{
    int v,w,nx;
}e[M];
int ne,h1[N],h2[N];

void Build1(int u,int v,int w)
{
    ++ne,e[ne]=(edge){v,w,h1[u]},h1[u]=ne;
}

void Build2(int u,int v,int w)
{
    ++ne,e[ne]=(edge){v,w,h2[u]},h2[u]=ne;
}

void Read()
{
    scanf("%d%d",&n,&m);
    int u,v,w;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&u,&v,&w);
        Build1(v,u,w),
        Build2(u,v,w);
    }
    scanf("%d%d%d",&s,&t,&k);
}

const int INF=99999999;
typedef pair<int,int> pr;
priority_queue<pr,vector<pr>,greater<pr> > Q;//坑了我一个下午，无奈……
int d[N]; bool v[N];
void Dijkstra()
{
    for(int i=1;i<=n;++i) d[i]=INF;
    d[t]=0;
    Q.push(make_pair(0,t));
    int nw;
    while(!Q.empty())
    {
        nw=Q.top().second; Q.pop();
        if(v[nw]) continue;
        v[nw]=1;
        for(int i=h1[nw];i;i=e[i].nx)
            if(d[e[i].v]>d[nw]+e[i].w)
            {
                d[e[i].v]=d[nw]+e[i].w;
                Q.push(make_pair(d[e[i].v],e[i].v));
            }
    }
}

struct node
{
    int id,g,f;
    bool operator < (node tmp) const
    {
        if(f==tmp.f) return g>tmp.g;
        return f>tmp.f;
    }
};
priority_queue<node> q;
int cnt[N];
void A_star()
{
    if(s==t) ++k;
    q.push((node){s,0,d[s]});
    int nw,dis;
    while(!q.empty())
    {
        nw=q.top().id,
        dis=q.top().g;
        q.pop();
        ++cnt[nw];
        if(cnt[nw]>k) continue;
        if(nw==t)
        {
            if(cnt[t]==k)
            {
                printf("%d\n",dis);
                return;
            }
        }
        for(int i=h2[nw];i;i=e[i].nx)
            q.push((node){e[i].v,dis+e[i].w,dis+e[i].w+d[e[i].v]});
    }
    puts("-1");
}

int main()
{
    Read(),Dijkstra(),A_star();
    return 0;
}