poj 2499第K短路模板

第k*短路模板（单项边）

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#define Max 100005

#define inf 1<<28

using namespace std;

int S,T,K,n,m;

int head[Max],rehead[Max];

int num,renum;

int dis[Max];

bool visit[Max];

int ans[Max];

int qe[Max*];

struct kdq{

    int v,len,next;

} edge[Max],reedge[Max];

struct a_star {               //A*搜索时的优先级队列;

    int v;

    int len;

    bool operator<(const a_star &a)const{    //f(i)=d[i]+g[i]

        return len+dis[v]>a.len+dis[a.v];

    }

};

void insert(int u,int v,int len){//正图和逆图

    edge[num].v=v;

    edge[num].len=len;

    edge[num].next=head[u];

    head[u]=num;

    num++;

    reedge[renum].v=u;

    reedge[renum].len=len;

    reedge[renum].next=rehead[v];

    rehead[v]=renum;

    renum++;

}

void init(){

    memset(ans,,sizeof(ans));

    for(int i=; i<=n; i++)

        head[i]=-,rehead[i]=-;

    num=,renum=;

}

void spfa(){//从T开始求出T到所有点的 dis[]

    int i,j;

    for(i=; i<=n; i++)

        dis[i]=inf;

    dis[T]=;

    visit[T]=;

    int num=,cnt=;

    qe[num++]=T;

    while(num>cnt){

        int temp=qe[cnt++];

        visit[temp]=;

        for(i=rehead[temp]; i!=- ; i=reedge[i].next){

            int tt=reedge[i].v;

            int ttt=reedge[i].len;

            if(dis[tt]>dis[temp]+ttt)

            {

                dis[tt]=dis[temp]+ttt;

                if(!visit[tt])

                {

                    qe[num++]=tt;

                    visit[tt]=;

                }

            }

        }

    }

}

int A_star(){

    if(S==T)

        K++;

    if(dis[S]==inf)

        return -;

    a_star n1;

    n1.v=S;

    n1.len=;

    priority_queue <a_star> q;

    q.push(n1);

    while(!q.empty()){

        a_star temp=q.top();

        q.pop();

        ans[temp.v]++;

        if(ans[T]==K)//当第K次取到T的时候，输出路程

            return temp.len;

        if(ans[temp.v]>K)

            continue;

        for(int i=head[temp.v]; i!=-; i=edge[i].next){

            a_star n2;

            n2.v=edge[i].v;

            n2.len=edge[i].len+temp.len;

            q.push(n2);

        }

    }

    return -;

}

int main(){

    int i,j,k,l;

    int a,b,s;

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

    init();

    while(m--){

        scanf("%d%d%d",&a,&b,&s);

        insert(a,b,s);

    }

    scanf("%d%d%d",&S,&T,&K);

    spfa();

    printf("%d\n",A_star());

    return ;

}