思路：
利用一个估计函数g[i]=dis[i]+len。其中len为队列出来的点当前已经走了的距离。dis[i]为该点到终点的最短路径。这样我们只要将点按g[i]的升序在队列你排序，每次取出最小的g[i]值的点。其意义就是每次找最短的能到终点的点。第一次找到就是最短路径，第二次就是就是第二短，第三次就是...顺推
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<queue> #define Maxn 1010 #define Maxm 200200 #define inf 10000000 using namespace std; int dis[Maxn],vi[Maxn],head[Maxn],e,map[Maxn][Maxn],n,m,cnt[Maxn]; struct Edge{ int u,v,next,val; }edge[Maxm]; struct Point{ int u,len; int operator <(const Point &temp) const { return len+dis[u]>temp.len+dis[temp.u]; } }; void init() { e=0; memset(dis,0,sizeof(dis)); memset(vi,0,sizeof(vi)); memset(head,-1,sizeof(head)); memset(cnt,0,sizeof(cnt)); for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) map[i][j]=inf; } } void add(int u,int v,int val) { edge[e].v=v;edge[e].val=val;edge[e].next=head[u];head[u]=e++; map[v][u]=(val<map[v][u]?val:map[v][u]); } void dijkstra(int s) { int i,j,u; for(int i=1;i<=n;i++) dis[i]=inf,vi[i]=0; for(i=1;i<=n;i++) dis[i]=map[s][i]; dis[s]=0; for(i=1;i<=n;i++) { int min=inf; for(j=1;j<=n;j++) if(!vi[j] && dis[j]<=min) { u=j; min=dis[j]; } if(min==inf) break; vi[u]=1; for(j=1;j<=n;j++) { if(!vi[j]&&dis[j]>dis[u]+map[u][j]) dis[j]=dis[u]+map[u][j]; } } } int A_star(int s,int t,int k) { priority_queue<Point> q; memset(vi,0,sizeof(vi)); Point a,p; a.u=s,a.len=0; q.push(a); while(!q.empty()) { a=q.top(); q.pop(); vi[a.u]++; if(vi[a.u]>k) continue; if(vi[t]==k) return a.len; for(int v=head[a.u];v!=-1;v=edge[v].next) { p.u=edge[v].v; p.len=a.len+edge[v].val; q.push(p); } } return -1; } int main() { int i,j,s,t,k,a,b,c; while(scanf("%d%d",&n,&m)!=EOF) { init(); for(i=1;i<=m;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c); } scanf("%d%d%d",&s,&t,&k); dijkstra(t); if(s==t) k++; if(dis[s]==inf) { printf("-1 "); continue; } printf("%d ",A_star(s,t,k)); } return 0; }