题目：就是求给出的两点之间的第k短的路，没有的话就输出-1
A*算法其实就是在搜索的时候有一个方向，计算出最可能是答案的解
/* F（p）=g（p）+h（p） g（p）为当前从s到p所走的长度，h（p）为从p到 t 的最短路的长度， 则F（p）的意义就是从s按照当前路径走到 p 后要走到终点 t 一共至少要走多远*/ #include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; const int maxx = 100010; const int inf = 0x3f3f3f3f; struct node { int f,g,v; }; bool operator < (node a,node b) { if(a.f==b.f)return a.g>b.g; return a.f>b.f; } struct edge { int v,next,w; }e1[maxx],e2[maxx]; int head1[maxx],head2[maxx],num=0; int n,m,s,t,k; int vis[1010],dis[1010]; void add(int u,int v,int w) { e1[++num].v=v;e1[num].w=w; e1[num].next=head1[u];head1[u]=num; e2[num].v=u;e2[num].w=w; e2[num].next=head2[v];head2[v]=num; } void spfa(int t)//就是求任意点到t的最短路，即h(p) { memset(dis,inf,sizeof(dis)); queue<int>q; q.push(t); dis[t]=0; while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0; for(int i=head2[u];i!=-1;i=e2[i].next) { int v=e2[i].v,w=e2[i].w; if(dis[v]>dis[u]+w) { dis[v]=dis[u]+w; if(!vis[v]) { q.push(v); vis[v]=1; } } } } } int Astar(int s,int t)//就是有方向的bfs { int cnt=0; priority_queue<node>q; if(s==t)k++; if(dis[s]==inf)return -1; node x,xx; x.v=s;x.g=0;x.f=x.g+dis[s]; q.push(x); while(!q.empty()) { xx=q.top();q.pop(); if(xx.v==t) { cnt++; if(cnt==k)return xx.g; } for(int i=head1[xx.v];i!=-1;i=e1[i].next) { x.v=e1[i].v; x.g=xx.g+e1[i].w; x.f=x.g+dis[x.v]; q.push(x); } } return -1; } int main() { cin>>n>>m; memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); int u,v,w; while(m--) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); } cin>>s>>t>>k; spfa(t); printf("%d ",Astar(s,t)); return 0; }