POJ2449 k短路问题

$A^{\star }$算法的经典应用----k短路问题。

$A^{\star }$算法：设$f(x)=g(x)+h(x)$，其中$g(x)$表示已花费代价，$h(x)$表示预估还需代价($h(x)$要$\le h^{\star }(x)$）表示每次找到f值最小的拿出来扩展。

给定一个n点m边的有向图，求从s到t的k短路。

首先求出所有点x到t的最短路$dis[x]$，接下来用$dis[x]$作为$h(x)$跑 $A^{\star }$ ，因为 $h(x)\le h^{\star }(x)$ ，所以第k次找到t就是k短路。

注意：一条路径至少有一条边，所以当s=t的时候第一次找到的路径不是真正的路径（因为一步都没走），也就是k要+1

代码：

/*
Author: CNYALI_LK
LANG: C++
PROG: poj2449.cpp
*/
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cctype>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
struct inout{
//吃掉io是我的习惯
};
inout io;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
int beg[1024],to[102424],lst[102424],w[102424],s,t,k;
int fbeg[1024],fto[102424],flst[102424],fw[102424],e,inq[1024],dis[1024];
int q[10024240];
void spfa(int s){//在反图中跑最短路
    int l,r;
    l=r=1;
    q[1]=s;
    while(l<=r){
        int u=q[l],v;
        inq[u]=0;
        for(int i=fbeg[u];i;i=flst[i]){
            v=fto[i];
            if(dis[v]>dis[u]+fw[i]){
                dis[v]=dis[u]+fw[i];
                if(!inq[v]){
                    inq[v]=1;
                    q[++r]=v;
                }
            }
        }
        ++l;
    }
}
typedef pair<int,pair<int,int> > pii;//形如(f(x),(g(x),x)) 
priority_queue<pii,vector<pii>,greater<pii> > pq;
#define x first
#define y second
#define mp make_pair
void add(int u,int v,int wea){//正边
    to[++e]=v;
    lst[e]=beg[u];
    w[e]=wea;
    beg[u]=e;
}
void fadd(int u,int v,int w){//反边
    fto[e]=v;
    flst[e]=fbeg[u];
    fw[e]=w;
    fbeg[u]=e;
}
void astar(int s){
    pq.push(mp(dis[s],mp(0,s)));
    pii u;
    int sx,v;
    if(dis[s]!=0x3f3f3f3f)
    while(!pq.empty()){
        u=pq.top();
        sx=u.y.x;
        pq.pop();
        if(u.y.y==t){
            --k;
            if(!k){
                io<<u.x<<endl;
                return;
            }
        }
        for(int i=beg[u.y.y];i;i=lst[i]){
            v=to[i];
            if(dis[v]!=0x3f3f3f3f)
            pq.push(mp(sx+w[i]+dis[v],mp(sx+w[i],v)));//扩展
        }
    }
    io<<-1<<endl;
}
int main(){
#ifdef cnyali_lk
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    io.init();
    int n,m,u,v,w;
    io>>n>>m;
    up(i,1,m){
        io>>u>>v>>w;
        add(u,v,w);
        fadd(v,u,w);
    }
    io>>s>>t>>k;
    if(s==t)++k;//注意
    up(i,1,n)dis[i]=0x3f3f3f3f;
    dis[t]=0;
    spfa(t);
    astar(s);
    io.out();
    return 0;
}