第k小路徑

description

給出一個有n個點的有向圖，求從s到t的第k小路徑。

Solution

我們可以将便全部反向，跑一下從終點到所有點的最短路。我們設一個點的估價函數g[i]=f[i]+d[i]，d[i]表示目前點到終點的距離，f[i]表示目前走到點i的距離。那麼我們每次從堆中取出估價函數最小的數，拿他擴充到别的點，并把它加入堆中。假設目前取到的點為終點，那麼我們就統計一下答案。

Code

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#define ll long long
using namespace std;
const int maxn=;
struct code{
    int a,b,c;
    bool friend operator < (code x,code y){
        if (x.a==y.a) return !(x.c<y.c);
        return !(x.a<y.a);
    }
}g;
priority_queue<code>f;
int first[maxn],last[maxn],next[maxn],d[maxn],value[maxn],v[maxn*];
int n,m,i,t,j,k,l,x,y,num,s,p,z,q,sum;
int first1[maxn],last1[maxn],next1[maxn],value1[maxn];
bool bz[maxn];
void lian(int x,int y,int z){
    last[++num]=y;value[num]=z;next[num]=first[x];first[x]=num;
}
void lian1(int x,int y,int z){
    last1[num]=y;value1[num]=z;next1[num]=first1[x];first1[x]=num;
}
void spfa(){
    int i=,j=,t,k,l,x,y;
    memset(d,,sizeof(d));
    v[]=q;bz[q]=true;d[q]=;
    while (i<j){
        x=v[++i];
        for (t=first1[x];t;t=next1[t]){
            if (d[last1[t]]<=d[x]+value1[t]) continue;
            d[last1[t]]=d[x]+value1[t];
            if (bz[last1[t]]) continue;
            v[++j]=last1[t];bz[last1[t]]=true;
        }
        bz[x]=false;
    }
}
int main(){
    //freopen("data.in","r",stdin);
    scanf("%d%d",&n,&m);
    for (i=;i<=m;i++)
        scanf("%d%d%d",&x,&y,&z),lian(x,y,z),lian1(y,x,z);
    scanf("%d%d%d",&s,&q,&sum);
    spfa();
    if (s==q) sum++;
    if (d[s]==){
        printf("-1\n");
        return ;
    }
    g.a=d[s];
    g.b=s;
    f.push(g); 
    while (!f.empty()){
        g=f.top();
        if (g.b==q){
            sum--;
            if (!sum){
                printf("%d\n",g.a);return ;
            }
        }
        x=g.b;
        k=g.a;
        l=g.c;
        f.pop();
        for (t=first[x];t;t=next[t]){
            g.a=l+value[t]+d[last[t]];
            g.b=last[t];
            g.c=l+value[t];
            f.push(g); 
        }

    }
    printf("-1\n");
}