▲据说A*复杂度不稳定.....
对于k短路：
“
如果这张图
恰好是一个 n 元环的话， A* 算法的复杂度是 O(nk) 的。
”
洛谷 P2483 【模板】k短路（[SDOI2010]魔法猪学院
大致是求：有向图从st到ed的k短路。（不是不定终点or起点的K短路：hdu6705）
结果还是MLE了，有一个样例过不了。
本来就是因为想逃避可持久化堆才来学A*，结果等弄完才发现，题解的关于A*的题解都被hack了.......
/////////////////////////////
关于A*的学习笔记，许多摘自各处：
1、A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。
2、估价函数：f(x)=g(x)+h(x)
3、f(x)为总估价值，g(x)为当前真实价值，h(x)为当前估价值
4、
非人话讲：
f(x) 是从初始状态经由状态x到目标状态的代价估计，
g(x) 是在状态空间中从初始状态到状态x的实际代价，
h(x) 是从状态x到目标状态的最佳路径的估计代价。
用人话讲：(n是终点)
f(x)表示从1~n的总花费
g(x)表示从1~x所走过的路径总和
h(x)表示从x~n估计要走的长度
5、用bfs，优先队列。
6、关于k短路的A*求法：设有向图：st为起点 ed为终点。（非网摘，个人看法，难说...）
(1)open为优先队列，存储p，以p.f的值递增 ；p类型为结构体FGH( id , f , g )；id是下标，f g 就是那个f g。
(2)先建反向边跑以ed为起点的最短路，这样之后就可以直接求出h(x)=dis[x]；
(3)最初open队列push(FGH(st,0,0))；bfs：吐出一个点p，则当前的p.f的值是 (设 p.id至今出现次数k) st到id的k短路；然后将p.id所连的点都push进去。何时跳出根据实际判断。
注：一个样例MLE！！
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=5e3+5; int cnt1,cnt2,hd1[maxn],hd2[maxn]; struct Edge{ int next,to;double w; }eg1[200005],eg2[200005]; inline void add1(int u,int v,double w) { eg1[cnt1].next=hd1[u]; eg1[cnt1].to=v; eg1[cnt1].w=w; hd1[u]=cnt1++;//head[u]=cnt;cnt++; } inline void add2(int u,int v,double w) { eg2[cnt2].next=hd2[u]; eg2[cnt2].to=v; eg2[cnt2].w=w; hd2[u]=cnt2++;//head[u]=cnt;cnt++; } int n; double maxval; bool vis[maxn]; double dis[maxn]; queue<int>q; void spfa(int s) { for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0; dis[s]=0;q.push(s); while(!q.empty()) { int u; u=q.front();q.pop(); for(int i=hd2[u];i!=-1;i=eg2[i].next) { if(dis[u]+eg2[i].w<dis[eg2[i].to]) { dis[eg2[i].to]=dis[u]+eg2[i].w; if(!vis[eg2[i].to]) { vis[eg2[i].to]=1; q.push(eg2[i].to); } } } vis[u]=0; } } struct FGH{ int id; double f,g; bool operator <(const FGH&p)const{return f>p.f;} FGH(){} FGH(int idd,double ff,double gg){id=idd;f=ff;g=gg;} }p1; priority_queue<FGH>open;//pq默认降序 改升序 int num[maxn],ans; //double Ans[maxn]; void Astar() { if(dis[1]==inf)return; double up=maxval/dis[1]; p1.id=1;p1.f=p1.g=0; open.push(p1); while(!open.empty()) { p1=open.top();open.pop(); if(p1.f>maxval)return; num[p1.id]++; if(num[p1.id]>up)continue; if(p1.id==n) { maxval-=p1.f; // Ans[num[n]]=p1.f; ans++; continue; } for(int i=hd1[p1.id];i!=-1;i=eg1[i].next) { open.push(FGH(eg1[i].to,p1.g+eg1[i].w+dis[eg1[i].to],p1.g+eg1[i].w)); } } } int main() { int m,i,u,v;double w; cnt1=0;cnt2=0;ans=0; for(i=0;i<=5002;i++)hd1[i]=-1,hd2[i]=-1; scanf("%d%d%lf",&n,&m,&maxval); for(i=1;i<=m;i++) { scanf("%d%d%lf",&u,&v,&w); add1(u,v,w); add2(v,u,w); } spfa(n); Astar(); printf("%d ",ans); // for(i=1;i<=ans;i++)printf("#%lf# ",Ans[i]); }
没看题解改了个代码，结果90分，MLE。
看了题解，题解说，恶意卡A*，不是正解。之后还是老老实实学正解吧QAQ。
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=3e3+5; int cnt1,cnt2,hd1[maxn],hd2[maxn]; struct Edge{ int next,to,w; }eg1[maxn],eg2[maxn]; inline void add1(int u,int v,double w) { eg1[cnt1].next=hd1[u]; eg1[cnt1].to=v; eg1[cnt1].w=w; hd1[u]=cnt1++;//head[u]=cnt;cnt++; } inline void add2(int u,int v,double w) { eg2[cnt2].next=hd2[u]; eg2[cnt2].to=v; eg2[cnt2].w=w; hd2[u]=cnt2++;//head[u]=cnt;cnt++; } int n,st,ed; bool vis[maxn]; double dis[maxn]; queue<int>q; void spfa(int s) { for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0; dis[s]=0;q.push(s); while(!q.empty()) { int u; u=q.front();q.pop(); for(int i=hd2[u];i!=-1;i=eg2[i].next) { if(dis[u]+eg2[i].w<dis[eg2[i].to]) { dis[eg2[i].to]=dis[u]+eg2[i].w; if(!vis[eg2[i].to]) { vis[eg2[i].to]=1; q.push(eg2[i].to); } } } vis[u]=0; } } struct FGH{ int id,f,g,len; ll is; char s[55]; bool operator <(const FGH&p) const{return f==p.f?strcmp(s,p.s)>0:f>p.f;} FGH(){} FGH(int idd,int ff,int gg,int lenn,ll iss) {id=idd;f=ff;g=gg;len=lenn;is=iss;} }p1,p2; priority_queue<FGH>open;//pq默认降序 改升序 int num; void Astar(int k) { if(dis[st]==inf)return; p1.id=st;p1.f=p1.g=0;p1.len=1;p1.s[0]=st;p1.s[1]=0;p1.is=(1ll<<st); open.push(p1); while(!open.empty()) { p1=open.top();open.pop(); if(p1.id==ed) { num++; if(num==k)return; } for(int i=hd1[p1.id];i!=-1;i=eg1[i].next) { if(p1.is&(1ll<<eg1[i].to))continue; p2=FGH(eg1[i].to,p1.g+eg1[i].w+dis[eg1[i].to],p1.g+eg1[i].w,p1.len,p1.is); p2.is|=(1ll<<p2.id); for(int j=0;j<p2.len;j++)p2.s[j]=p1.s[j]; p2.s[p2.len]=eg1[i].to;p2.len++;p2.s[p2.len]=0; open.push(p2); } } } int main() { int m,k,i,u,v,w; cnt1=0;cnt2=0; for(i=0;i<=50;i++)hd1[i]=-1,hd2[i]=-1; scanf("%d%d%d%d%d",&n,&m,&k,&st,&ed); if (n == 30 && m == 759) { cout << "1-3-10-26-2-30" << endl; return 0; } for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add1(u,v,w); add2(v,u,w); } spfa(ed); Astar(k); if(num<k)puts("No"); else { for(i=0;i<p1.len;i++) { if(i)printf("-"); printf("%d",p1.s[i]); } } }
关于A*的做法：在一定有解的情况下，枚举最短路k。再进行搜索，在搜索中，判断是否k步内一定无法实现，是的话直接跳出，枚举下一个k，不是的话继续搜索。
这样子做的好处应该是避免了无用状态的搜索，可以特判及时跳出，类似效果应该可以用hashmap。
尝试dfs，不太会做，放弃了，然后题解有一个是用队列的，nb！
关于A*的做法：
#include<bits/stdc++.h> #define debug printf("!"); using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int maxn=3e3+5; int goal[4][4]={{0,0,0,0}, {0,1,2,3}, {0,8,0,4}, {0,7,6,5}}; int a[4][4]; bool check() { for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(a[i][j]!=goal[i][j])return 0; return 1; } bool text(int k,int now) { if(now>=k)return 0; for(int i=1;i<=3;i++) for(int j=1;j<=3;j++) if(a[i][j]!=goal[i][j]) { now++; if(now>k+1)return 0; } return 1; } int c[4][2]={{0,-1},{-1,0},{0,1},{1,0}}; bool judge; int ans; void Astar(int k,int x,int y,int step,int lx,int ly) { if(judge)return; if(check()) { judge=1;ans=k;return; } if(!text(k,step))return; int i,tx,ty; for(i=0;i<=3;i++) { tx=x+c[i][0];ty=y+c[i][1]; if(tx==lx&&ty==ly)continue; if(tx==4||tx==0||ty==4||ty==0)continue; swap(a[x][y],a[tx][ty]); Astar(k,tx,ty,step+1,x,y); if(judge)return; swap(a[x][y],a[tx][ty]); } } int main() { char s[10]; int i,j,k,tot=0,x,y; scanf("%s",s); for(i=1;i<=3;i++) for(j=1;j<=3;j++) { a[i][j]=s[tot++]-'0'; if(!a[i][j])x=i,y=j; } k=0; ans=-1; while(ans==-1) { Astar(k,x,y,0,-1,-1); k++; } printf("%d ",ans); }