//题目类型：求K最短路//算法实现：Dijkstra+A*(启发式搜索)//首先求出其他点到des的最短距离，然后用基于BFS的优先队列A*算法求，f(i)=g(i)+h(i) 其中h(i)表示i到des的最短路，g(i)表示从src到i的//路径长度每次取出f(i)值最小的，当第k次取出t时即求出第k短路#include <iostream>#include <queue>//#include <conio.h>using namespace std;#define marray 100001#define narray 1001const int maxData = 0x7fffffff;typedef struct edge{ int v; int w; edge *next;}edge;edge *adj[narray],*readj[narray],edges[marray],reedges[marray]; //正向邻接表指针，逆向邻接表指针，正向边，逆向边 typedef struct dijedge //Dijstra求最短路时优先级队列 { int v; int w; bool operator <(const dijedge & a) const { return w>a.w; }}dijedge;int edgenum,reedgenum;int n,m;int d[narray];bool final[narray];int cnt[narray]; //A*搜索时记录入队列次数 int src,des,k;typedef struct aedge //A*搜索时的优先级队列 { int v; int w; bool operator<(const aedge &a)const //f(n)=d[i]+g[i] { return w+d[v]>a.w+d[a.v]; } }aedge;void addEdge(int start,int end,int w){ edge *ptr = &edges[edgenum++]; ptr->v = end; ptr->w = w; ptr->next = adj[start]; adj[start] = ptr;}void addReEdge(int start,int end,int w){ edge *ptr =&reedges[reedgenum++]; ptr->v = end; ptr->w = w; ptr->next = readj[start]; readj[start] = ptr;}void Dij(int src){ int i,j; dijedge tempedge; priority_queue<dijedge> myqueue; memset(final,0,sizeof(final)); for(i=1;i<=n;++i) d[i] = maxData; d[src] = 0; final[src] = true; tempedge.v=src; tempedge.w=0; myqueue.push(tempedge); while(!myqueue.empty()) { int frontv = myqueue.top().v; int frontw = myqueue.top().w; myqueue.pop(); final[frontv] = true; for(edge *p = readj[frontv];p;p=p->next) { int tempv= p->v; int tempw= p->w; if(!final[tempv] && d[tempv]>d[frontv]+tempw) { d[tempv] = d[frontv]+tempw; tempedge.v = tempv; tempedge.w = d[tempv]; myqueue.push(tempedge); } } }}int a_star(){ aedge tempaedge; priority_queue<aedge> myqueue; memset(cnt,0,sizeof(cnt)); //记录顶点的入队列次数 if(d[src]==maxData) return -1; if(src==des) k++; //考虑终点和源点相同的情况，针对题目要求 tempaedge.v = src; tempaedge.w = 0; myqueue.push(tempaedge); while(!myqueue.empty()) { int frontv = myqueue.top().v; int frontw = myqueue.top().w; myqueue.pop(); cnt[frontv]++; if(cnt[des]==k) return frontw; //终点入队列k次，说明找到了K最短路 if(cnt[frontv]>k) continue; for(edge *p = adj[frontv];p;p=p->next) { tempaedge.v = p->v; tempaedge.w = frontw + p->w; myqueue.push(tempaedge); } } return -1;}int main(){ //freopen("1.txt","r",stdin); int i,j; int start,end,value; while(scanf("%d%d",&n,&m)!=-1) { edgenum = 0; reedgenum = 0; for(i=1;i<=n;++i) { adj[i] = NULL; readj[i] = NULL; } for(i=1;i<=m;++i) { scanf("%d%d%d",&start,&end,&value); addEdge(start,end,value); addReEdge(end,start,value); } scanf("%d%d%d",&src,&des,&k); Dij(des); //求出终点到其他点的最短路（利用逆向邻接表实现） printf("%d\n",a_star()); } //getch(); return 0;}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/06/05/1752255.html
相关资源：数据结构—成绩单生成器