采用A*算法的k短路模板
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
using namespace std;
const int MAXN=200005;
int init(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<3)+(rv<<1)+c-'0';
c=getchar();
}
return rv*fh;
}
int disk[MAXN],s,t,k,dis[MAXN],head1[MAXN],head[MAXN],nume,n,m;
struct edge{
int to,nxt,dis;
}e[MAXN],e1[MAXN];
void adde(int from,int to,int dis){
e[++nume].to=to;
e[nume].dis=dis;
e[nume].nxt=head[from];
head[from]=nume;
}
void adde1(int from,int to,int dis){
e1[++nume].to=to;
e1[nume].dis=dis;
e1[nume].nxt=head1[from];
head1[from]=nume;
}
struct cmp{
bool operator ()(const int &a,const int &b) const {
return dis[a]>dis[b];
}
};
struct node{
int v,f,g;
bool operator < (const node &a)const{
if(a.f==f) return a.g<g;
return a.f<f;
}
};
void dij(){
priority_queue<int,vector<int>,cmp> q;
memset(dis,0x3f,sizeof(dis));
dis[t]=0;
q.push(t);
while(!q.empty()){
int u=q.top();q.pop();
for(int i=head1[u];i;i=e1[i].nxt){
int v=e1[i].to;
if(dis[v]>dis[u]+e1[i].dis){
dis[v]=dis[u]+e1[i].dis;
q.push(v);
}
}
}
}
int A_star(){
if(s==t) k++;
int cnt[MAXN];
if(dis[s]==0x3f3f3f3f) return -1;
memset(cnt,0,sizeof(cnt));
priority_queue <node> q;
q.push({s,dis[s],0});
while(!q.empty()){
node u=q.top();q.pop();
cnt[u.v]++;
if(u.v==t&&cnt[u.v]==k) return u.g;
if(cnt[u.v]>k) continue;
for(int i=head[u.v];i;i=e[i].nxt){
q.push({e[i].to,u.g+e[i].dis+dis[e[i].to],u.g+e[i].dis});
}
}
return -1;
}
int main(){
n=init();m=init();
for(int i=1;i<=m;i++){
int u=init(),v=init(),di=init();
adde1(v,u,di);
}
s=init();t=init();k=init();
dij();
nume=0;
for(int i=1;i<=n;i++){
for(int j=head1[i];j;j=e1[j].nxt){
adde(e1[j].to,i,e1[j].dis);
}
}
//for(int i=1;i<=n;i++) for(int j=head[i];j;j=e[j].nxt) cout<<e[j].to<<endl;
int ans=A_star();
// cout<<dis[s]<<endl;
// cout<<dis[t]<<endl;
printf("%d\n",ans);
return 0;
}