Remmarguts' Date POJ - 2449 第k短路 SPFA+A*

這是一道巧妙利用了A*算法的一道題

A*算法比較開心的地方是在算出最短路的時候,繼續算下去會得到次最短路,繼續下去是次次最短路,….所有可能的路.

在A*算法中 F(x)=G(x)+H(x)

其中G(x) 表示到x後已經走了的距離

H(x) 表示到x後再到終點估計要走多少(本題可以精确算出用SPFA)

F(x) 即是走這條路到達的期望距離

一個比較給力的剪枝 每個點通路k次就好了,多餘的并沒有對答案有任何的貢獻

代碼如下:

/*
 * Author       :  Echo
 * Email        :  [email protected]  
 * Description  :   
 * Created Time :  2017/10/5 10:36:41
 * Last Modify  :  2017/10/5 20:26:55
 * File Name    :  k_thRoad.cpp
 */
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
#define LL long long
#define mem(a,k) memset(a,k,sizeof(a))
using namespace std;
const int maxint = ->>;
const int maxn=+;
const int maxm=+;
int H[maxn],vis[maxn];
int cnt[maxn];
struct node{
    int f,g,s;
    friend bool operator<(node a,node b){
        return a.f>b.f;
    }
};
struct edge{
    int to,value,next;
    void set(int a,int b,int c){
        to=a,value=b,next=c;
    }
}an[maxm],bn[maxm];
int heada[maxn],cnta,headb[maxn],cntb;
int n,m;
int s,t,k;
void addedge(int u,int v,int value){
    an[cnta].set(v,value,heada[u]);
    heada[u]=cnta++;
    bn[cntb].set(u,value,headb[v]);
    headb[v]=cntb++;
}
void getH(){//spfa
    for(int i=;i<=n;i++) H[i]=;
    H[t]=;
    vis[t]=;
    queue<int> que;
    que.push(t);
    while(!que.empty()){
        int u=que.front();
        que.pop();
        vis[u]=;
        for(int i=headb[u];i!=-;i=bn[i].next){
            int v=bn[i].to;
            if(H[v]>H[u]+bn[i].value){
                H[v]=H[u]+bn[i].value;
                if(!vis[v])que.push(v),vis[v]=;
            }
        }
    }
}
int A_star(){
    getH();
    //for(int i=1;i<=n;i++){
        //printf("%d ",H[i]);
    //}
    //cout<<endl;
    priority_queue<node>que;
    node now;
    now.g=;
    now.s=s;
    now.f=now.g+H[now.s];
    que.push(now);
    while(!que.empty()){
        now=que.top();
        que.pop();
        cnt[now.s]++;
        if(cnt[now.s]>k) continue;
        //printf("test 1:%d %d %d\n",now.s,now.g,now.f);
        node nxt;
        if(now.s==t&&cnt[now.s]==k)return now.f;
        for(int i=heada[now.s];i!=-;i=an[i].next){
            if(H[an[i].to]==)continue;
            nxt.g=now.g+an[i].value;
            nxt.s=an[i].to;
            nxt.f=nxt.g+H[nxt.s];
            //printf("test 2:%d %d %d\n",nxt.s,nxt.g,nxt.f);
            que.push(nxt);
        }
    }
    return -;
}
int main(){
    cin>>n>>m;
    memset(heada,-,sizeof(heada));
    memset(headb,-,sizeof(headb));
    for(int i=;i<=m;i++){
        int a,b,v;
        scanf("%d%d%d",&a,&b,&v);
        addedge(a,b,v);
    }
    scanf("%d%d%d",&s,&t,&k);
    if(s==t)k++;
    printf("%d",A_star());
    return ;
}

/*
7 8
1 2 2
2 4 2
4 5 2
5 7 2
1 3 2
3 2 2
4 6 1
2 1 2
1 1 2

 */