[第K短路]POJ_2449_Remmarguts' Date

这里的第K短路的定义是：

1.如果起点终点相同，那么0并不是最短路，而是要出去一圈回来之后才是最短路，那么第K短路也是一样。

2.每个顶点和每条边都可以使用多次。（可以存在环和来回走）

然后求K短路使用A*算法，其估价函数f(n) = g(n)+h(n)，h(n)是终点到结点n的最短路径，g(n)是起点到结点n的实际代价， 这样选择显然能满足A*估价函数的要求，g(n)>=g'(n)，

h(n)<=h'(n)。

h(n)可以对原图的逆图进行SPFA得出。

终止条件是，如果终点第K次出队的话，那么表明已经找到第K短路。

注意处理起点终点不连通的情况。

很裸的K短路题。

传送门：http://poj.org/problem?id=2449

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 1111,MAXM = 111111;
struct edge{
    int v,w,nxt;
    edge(){}
    edge(int vv,int ww):v(vv),w(ww){}
}rst[MAXM<<1],sec[MAXM<<1];
struct node{
    int f,g,v;
    node(){}
    node(int ff,int gg,int vv):f(ff),g(gg),v(vv){}
    bool operator < (const node &n) const{
        return n.f<f;
    }
};
int hrst[MAXN],hsec[MAXN],dist[MAXN],inQ[MAXN],n,m,s,t,k,ecnt;
void init(){
    memset(hrst,-1,sizeof(hrst));
    memset(hsec,-1,sizeof(hsec));
    ecnt = 0;
    fill(dist,dist+MAXN,0x3fffffff);
    memset(inQ,0,sizeof(inQ));
}
void add(int u,int v,int w){
    rst[ecnt] = edge(v,w);
    sec[ecnt] = edge(u,w);
    rst[ecnt].nxt = hrst[u];
    sec[ecnt].nxt = hsec[v];
    hrst[u] = ecnt;
    hsec[v] = ecnt++;
}
void SPFA(int src){
    queue<int> Q;
    Q.push(src);inQ[src]=1;
    dist[src]=0;
    while(!Q.empty()){
        int cur = Q.front();
        Q.pop();inQ[cur]=0;
        for(int i=hsec[cur];i!=-1;i=sec[i].nxt){
            if(dist[sec[i].v]>dist[cur]+sec[i].w){
                dist[sec[i].v] = dist[cur]+sec[i].w;
                if(!inQ[sec[i].v])inQ[sec[i].v]=1,Q.push(sec[i].v);
            }
        }
    }
}
int Astar(int src,int dest){
    priority_queue<node> PQ;
    if(dist[src]==0x3fffffff)return -1;//不可达
    memset(inQ,0,sizeof(inQ));
    PQ.push(node(dist[src],0,src));
    while(!PQ.empty()){
        node cur = PQ.top();
        PQ.pop();inQ[cur.v]++;
        //cout<<cur.f<<" "<<cur.v<<" "<<dest<<" "<<inQ[dest]<<endl;
        if(inQ[dest]==k)return cur.f;
        if(inQ[cur.v]>k)continue;//don't process this case when a node out of queue more then k times
        for(int i=hrst[cur.v];i!=-1;i=rst[i].nxt){
            node next(dist[rst[i].v]+rst[i].w+cur.g,cur.g+rst[i].w,rst[i].v);
            PQ.push(next);//expand new node;
        }
    }
    return -1;
}
int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        init();
        while(m--){
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);a--,b--;
            add(a,b,c);
        }
        scanf("%d%d%d",&s,&t,&k);s--,t--;
        SPFA(t);
        if(s==t)k++;//如果起点终点相同，0不是第1短路径。。
        printf("%d\n",Astar(s,t));
    }
    return 0;
}