A_star裸题
先反向建边跑一边spfa,然后把某点目前从起点跑的距离+它到终点的最短距离作为估价来跑A_star
//Twenty
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
const int maxn=1000+299;
const int maxm=10000*2+299;
const int INF=1e9+7;
int n,m,k,x,y,z,fir[maxn],nxt[maxm],to[maxm],val[maxm],e[maxm][3],vis[maxn],out[maxn],ecnt,s,t;
int tot,ans[maxm];
using namespace std;
void add(int u,int v,int w) {
nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w;
}
struct node{
int id,real,dis;
node(){}
node(int id,int real,int dis):id(id),real(real),dis(dis){}
friend bool operator <(const node&a,const node&b) {
return a.real+a.dis>b.real+b.dis;
}
}p[maxn];
queue<int>q;
void spfa() {
for(int i=1;i<=n;i++) p[i].dis=INF,vis[i]=0;
vis[t]=1; p[t].dis=0;
q.push(t);
while(!q.empty()) {
int now=q.front();
q.pop(); vis[now]=0;
for(int i=fir[now];i;i=nxt[i])
if(p[to[i]].dis>p[now].dis+val[i]) {
p[to[i]].dis=p[now].dis+val[i];
if(!vis[to[i]]) {
vis[to[i]]=1;
q.push(to[i]);
}
}
}
}
priority_queue<node>que;
void A_star() {
for(int i=1;i<=n;i++) p[i].id=i;
que.push(p[s]);
while(!que.empty()) {
node now=que.top();
que.pop();
if(++out[now.id]>k) continue;
if(now.id==t) {
ans[++tot]=now.real;
if(tot>=k) return;
}
for(int i=fir[now.id];i;i=nxt[i]) {
que.push(node(to[i],now.real+val[i],p[to[i]].dis));
}
}
}
int main() {
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m;i++) {
scanf("%d%d%d",&x,&y,&z);
add(y,x,z);
e[i][0]=x; e[i][1]=y; e[i][2]=z;
}
s=n; t=1;
spfa();
memset(fir,0,sizeof(fir));
memset(vis,0,sizeof(vis));
for(int i=1;i<=m;i++)
add(e[i][0],e[i][1],e[i][2]);
A_star();
for(int i=1;i<=k;i++){
if(i>tot) printf("-1
");
else printf("%d
",ans[i]);
}
return 0;
}