poj 2449 Remmarguts' Date (K短路+A*+Dijkstra)

題目連結:    http://poj.org/problem?id=2449

題目大意:    在一個有N個點M條邊的有向連通圖裡

                   找到S到T的第k短路的長度

解題思路:    經典的k短路A*算法題

                   估價函數: f[x]=h[x]+g[x]

                   f[x]:  估計經過該點的路線到達T點最小需要經過的路徑長度 (大于或等于實際最短長度)

                   h[x]:  從起點到該點實際走的長度 (已經走了)

                   g[x]:  估計從該點到達終點經過的最小長度 (還沒走的)

                   f[x]是實際走的，也就是BFS的目前路徑長度

                   而g[x]可以用Dijkstra反向建邊求終點到達其他所有點的最短距離

                   最小優先隊列每次出隊列的是f[x]最小的

                   BFS出隊列代表走到這個點

                   第一次出隊列是最短路，第二次出隊列是次短路，第k次也就是k短路！！！

                   當S==T時，k++，為什麼呢？因為第一次出隊列的就是終點，顯然隻是在原地打轉，沒有實際的路線

代碼:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
#define MAX 1001
typedef struct node{
    int v,h,g,f;
    friend bool operator < (node a,node b)  //最小優先隊列
    {
        return a.f>b.f;
    }
}snode;
struct ArcNode{
    int to,weigh;
    struct ArcNode *next;
};

struct ArcNode *listb[MAX];   //正向建邊用鄰接表解決重邊問題
int n,m,dist[MAX],visit[MAX]={0},ant[MAX]={0},edge2[MAX][MAX];

void Dijkstra(int v0)         //終點到其他所有點的最短距離，構造g[]
{
    int i,j,min,minv;
    for(i=1;i<=n;i++)
    {
        edge2[i][i]=0;
        dist[i]=edge2[v0][i];
    }
    for(i=1;i<=n;i++)
    {
        min=INF;
        minv=v0;
        for(j=1;j<=n;j++)
        {
            if(dist[j]<min&&!visit[j])
            {
                min=dist[j];
                minv=j;
            }
        }
        visit[minv]=1;
        for(j=1;j<=n;j++)
        {
            if(!visit[j]&&edge2[minv][j]<INF&&dist[minv]+edge2[minv][j]<dist[j])
            {
                dist[j]=dist[minv]+edge2[minv][j];
            }
        }
    }
    return ;
}
int Astar(int sv,int ev,int k)
{
	snode v,tempv;
    struct ArcNode *temp;
    priority_queue<snode>q;
	v.v=sv; v.h=0; v.g=dist[sv]; v.f=v.h+v.g;  //初始化
	q.push(v);
	while(!q.empty())
	{
		v=q.top();
		q.pop();
        ant[v.v]++;
        if(ant[v.v]>k) continue;    //這個點通路次數超過k肯定不在這k條路上
		if(ant[v.v]==k&&v.v==ev) return v.h;  //第k次到達終點，傳回實際走的長度
        temp=listb[v.v];
        while(temp!=NULL)
        {
            tempv.v=temp->to;          //與之相連的點入隊列
            tempv.h=v.h+temp->weigh;   //新點的h[x]=h[x']+xx'
            tempv.g=dist[temp->to];    //新點的g[x]=dist[x]
            tempv.f=tempv.h+tempv.g;   //新點的f[x]=h[x]+g[x]
            q.push(tempv);             //與之相連的點入隊列
            temp=temp->next;
        }
	}
	return -1;
}

int main()
{
    int i,a,b,c;
    struct ArcNode *temp;
    scanf("%d%d",&n,&m);
    memset(edge2,INF,sizeof(edge2));
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        temp=(struct ArcNode*)malloc(sizeof(struct ArcNode));  //正向建邊
        temp->to=b; temp->weigh=c; temp->next=NULL;
        if(listb[a]==NULL)
            listb[a]=temp;
        else
        {
            temp->next=listb[a];
            listb[a]=temp;
        }
        if(edge2[b][a]>c)  //反向建邊,重邊取最小的邊
           edge2[b][a]=c;
    }
    scanf("%d%d%d",&a,&b,&c);
    if(a==b)    //陷阱
        c++;
    Dijkstra(b);
    printf("%d\n",Astar(a,b,c));
    return 0;
}
           

注：原創文章，轉載請注明出處