学步园

题目链接:    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;
}

注：原创文章，转载请注明出处