poj2449 Remmarguts' Date --- k短路模板（SPFA+A*） - c++编程基础

给一个图，起点s、终点t、k，求起点到终点的第k短路。

基本思路：

首先反向图中求出终点 t 到其他所有点的距离（预处理优化），

再从起点开始使用优先队列进行宽搜，用cnt记录到达终点的次数，当cnt==k时的路径长度即为所得。

搜索的方向用一个估价函数 f=g+h 来确定，其中g表示到当前点的路径长度，h表示当前点到终点的最短路径，即之前的预处理。

A*算法结合了启发式搜索（充分利用题目所给信息来动态的做出决定，使搜索次数大大降低），和形式化方法（不利用图给出的信息，仅利用数学的形式分析，如dij算法）。

它通过一个估价函数 f(h) 来决定搜索方向。估价函数=当前值+当前位置到终点的距离，每次扩展估价函数值最小的一个。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #define inf 0x3f3f3f3f #define ll long long #define mod 1000000007 using namespace std; const int maxn=1010; int d[maxn],head[maxn],head2[maxn],n,m,h; bool vis[maxn]; struct node { int v,w,next; }e[100010],e2[100010]; struct node1 { int v,g,f;// f=g+h bool operator < (const node1 &r) const { if(r.f==f) return r.g
           
             q; d[s]=0; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head2[now];i!=-1;i=e2[i].next) { if(d[now]+e2[i].w
            
              q; int cnt=0; node1 tmp,to; tmp.v=s; tmp.g=0; tmp.f=tmp.g+d[tmp.v]; q.push(tmp); while(!q.empty()) { tmp=q.top(); q.pop(); if(tmp.v==t) cnt++; if(cnt==k) return tmp.g; for(int i=head[tmp.v];i!=-1;i=e[i].next) { to.v=e[i].v; to.g=tmp.g+e[i].w; to.f=to.g+d[to.v]; q.push(to); } } return -1; } int main() { int u,v,w,s,t,k; while(~scanf("%d%d",&n,&m)) { init(); for(int i=0;i