#include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; typedef pair<int,PII> PIII; const int N=1010,M=2e5+10; int head1[M<<1],head2[M<<1]; struct node{ int next,to,val; }edge[M<<1]; int uuu,S,T; void add(int *head,int from,int to,int val){ edge[++uuu]={ head[from],to,val }; head[from]=uuu; } int dis[M<<1]; bool vis[M<<1]; void dij() { priority_queue<PII,vector<PII>,greater<PII>>q; q.push({0,T});///距离,标号 memset(dis,0x3f,sizeof dis); dis[T]=0; while(!q.empty()){ auto temp=q.top();q.pop(); if(vis[temp.second])continue; vis[temp.second]=true; for(int i=head2[temp.second];i;i=edge[i].next){ int x=edge[i].to; if(dis[x]>dis[temp.second]+edge[i].val){ dis[x]=dis[temp.second]+edge[i].val; q.push({dis[x],x}); } } } } int K; int astar(){ priority_queue<PIII,vector<PIII>,greater<PIII>>q; q.push({dis[S],{0,S}});///估计值,真实值,标号 int cnt=0; if(dis[S]==0x3f3f3f3f)return -1; while(!q.empty()){ auto temp=q.top();q.pop(); int x=temp.second.second,y=temp.second.first; if(x==T)cnt++; if(cnt==K)return y; for(int i=head1[x];i;i=edge[i].next){ int xx=edge[i].to; q.push({dis[xx]+y+edge[i].val,{y+edge[i].val,xx}}); } } return -1; } int main() { ios_base::sync_with_stdio(false); int n,m; cin>>n>>m; for(int i=0,u,v,val;i<m;i++){ cin>>u>>v>>val; add(head1,u,v,val); add(head2,v,u,val); } cin>>S>>T>>K; if(S==T)K++; dij(); cout<<astar(); }
原文:https://www.cnblogs.com/qq1415584788/p/14708461.html