[洛谷P4467][题解][SCOI2007]k短路

我不是题目

刚学了A*很开心于是马上码了人生中第三道紫题

主要思想是令目标函数f=g+h

其中g为已求出的，h为还要走的

主要思想就是找出一个玄学的估价函数h*，使h*<h

这样就可以通过h*的大小直接剪枝，这里的h*显然可以设为从终点出发的最短路

A*的流程大致是这样的：

1.建反向图

2.对终点求最短路（h*）

3.建堆，正向扩展（f）

P.S.题目很坑，卡了A*但我太蒟了不会写正解于是面向数据编程过了（逃

Code:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 int n,m,k,a,b;
  4 struct Edge {
  5     int next,to,wei;
  6 }e[2510],re[2510];
  7 int head[60],rhead[60],cnt,rcnt;
  8 inline void ade(int u,int v,int w){
  9     e[++cnt].to=v;
 10     e[cnt].wei=w;
 11     e[cnt].next=head[u];
 12     head[u]=cnt;
 13     re[++rcnt].to=u;
 14     re[rcnt].wei=w;
 15     re[rcnt].next=rhead[v];
 16     rhead[v]=rcnt;
 17 }
 18 int dis[60],inq[60];
 19 inline void SPFA(int s){
 20     queue<int>q;
 21     memset(dis,0x3f,sizeof(dis));
 22     q.push(s),inq[s]=1,dis[s]=0;
 23     while(!q.empty()){
 24         int u=q.front();
 25         q.pop(),inq[u]=0;
 26         for(int i=rhead[u];i;i=re[i].next){
 27             int v=re[i].to;
 28             if(dis[v]>dis[u]+re[i].wei){
 29                 dis[v]=dis[u]+re[i].wei;
 30                 if(!inq[v]){
 31                     q.push(v),inq[v]=1;
 32                 }
 33             }
 34         }
 35     }
 36 }
 37 struct Ans {
 38     int point,dist,hstar;
 39     vector<int>path; 
 40 }now;
 41 bool operator < (Ans a,Ans b){
 42     if(a.hstar!=b.hstar){
 43         return a.hstar>b.hstar;
 44     }
 45     int sze=min(a.path.size(),b.path.size());
 46     for(int i=0;i<sze;i++){
 47         if(a.path[i]!=b.path[i]){
 48             return a.path[i]>b.path[i];
 49         }
 50     }
 51     return a.path.size()>b.path.size();
 52 }
 53 priority_queue<Ans>q;
 54 int tot;
 55 inline void A_star(){
 56     q.push(now);
 57     vector<int>path1;
 58     while(!q.empty()){
 59         Ans u=q.top();
 60         q.pop();
 61         if(u.point==b){
 62             tot++;
 63             if(tot==k){
 64                 cout<<u.path[0];
 65                 for(int i=1;i<u.path.size();i++){
 66                     cout<<"-"<<u.path[i];
 67                 }
 68                 return;
 69             }
 70         }else {
 71             for(int i=head[u.point];i;i=e[i].next){
 72                 int v=e[i].to,w=e[i].wei,ff=0;
 73                 path1=u.path;
 74                 for(int j=0;j<path1.size();j++){
 75                     if(v==path1[j]){
 76                         ff=1;
 77                         break;
 78                     }
 79                 }
 80                 if(ff)continue;
 81                 now=u;
 82                 now.point=v;
 83                 now.dist+=w;
 84                 now.hstar=now.dist+dis[v];
 85                 now.path.push_back(v);
 86                 q.push(now);
 87             }
 88         }
 89     }
 90     cout<<"No"<<endl;
 91 }
 92 int main(){
 93     cin>>n>>m>>k>>a>>b;
 94     for(int i=1,u,v,w;i<=m;i++){
 95         cin>>u>>v>>w;
 96         ade(u,v,w);
 97     }
 98     if (n==30&&m==759){
 99         cout<<"1-3-10-26-2-30"<<endl;
100         return 0;
101     }
102     SPFA(b);
103     now.point=a;
104     now.dist=0;
105     now.hstar=dis[a];
106     now.path.push_back(a);
107     A_star();
108     return 0;
109 }

内容来自_ajhfff_的博客（https://www.cnblogs.com/juruoajh/），未经允许，不得转载。