题意：找第K短路的值
思路：A*，，bfs找K短路的时候加上估计函数（距离下界），而且要满足：cost(u,v)+h*(u)-h*(v)>=0
因为这是bfs’需要的下界函数，不是任何下界都可以，不像IDA*，这里的下界必须让每个bfs的节点保持原样的大小关系
而IDDFA中的A*下界函数就不需要这个性质了，只要是下界即可。
显然这个具体问题的天然的估计函数就是从此点到目标点的最短路。
#include<cstdio>#include<iostream>#include<cstring>#include<algorithm>#include<queue>using namespace std;const int M =1e5+100;const int N =1e3+10;const int inf = 0x3f3f3f3f ;struct Edge{int v;int w;int next;}es1[M],es2[M];int head1[N],head2[N];int n,m;int s,g,k;bool vis[N];int dis[N];void spfa(){memset(vis,0,sizeof(vis));dis[g]=0;queue<int >q;q.push(g);vis[g]=true;while(!q.empty()){int cur=q.front();q.pop();vis[cur]=false;for(int i=head2[cur];~i;i=es2[i].next){int v=es2[i].v,w=es2[i].w;if(dis[v]>dis[cur]+w){dis[v]=dis[cur]+w;if(vis[v]) continue;vis[v]=true;q.push(v);}}}}struct node{int u;int g,f;bool operator < (const node &a) const{return a.f<f; //按f最小堆}};int A_star(){int cnt=0;priority_queue<node> que;if(dis[s]==inf) return -1; //剪枝node st;st.g=0,st.f=dis[s],st.u=s;que.push(st);while(!que.empty()){node cur=que.top();que.pop();if(cur.u==g) cnt++;if(cnt==k) return cur.g;for(int i=head1[cur.u];~i;i=es1[i].next){int v=es1[i].v,w=es1[i].w;node nxt;nxt.u=v,nxt.g=cur.g+w,nxt.f=nxt.g+dis[v];que.push(nxt);}}return -1;}void ini(){fill(dis,dis+1005,inf);memset(head1,-1,sizeof(head1));memset(head2,-1,sizeof(head2));}int main(){while(~scanf("%d%d",&n,&m)){ini();for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);es1[i].v = v,es1[i].w=w,es1[i].next=head1[u];head1[u]=i;es2[i].v=u,es2[i].w=w,es2[i].next=head2[v];head2[v]=i;}scanf("%d%d%d",&s,&g,&k);if(s==g) k++; //易错，当s和g重合时，没经过其他路不算一种方法spfa();printf("%d\n",A_star());}return 0;}
人生最好的旅行，就是你在一个陌生的地方，
