安利一下自己博克https://www.cnblogs.com/Hale522520/

明明输出答案是对的 非要W 求助
#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
#define road 10000+10
#define node 1000+10
struct Edge
{
int x,y,z,next;
Edge(int x=0,int y=0,int z=0,int next=0):
x(x),y(y),z(z),next(next){}
}edge[road];
struct date
{
int x,g,h;
bool operator < (const date &a) const
{
return g+h>a.g+a.h;
}
};
int nl,m,k,x,y,z,sumedge,s,e,size;
int head[node],ans[100+10],dis[node],cnt[node];
bool vis[node];
int add(int x,int y,int z)
{
edge[++sumedge]=Edge(x,y,z,head[x]);
return head[x]=sumedge;
}
void spfa()
{
queue <int> q;
memset(dis,127/3,sizeof(dis));
dis[s]=0;vis[s]=1;q.push(s);
while(!q.empty())
{
int now=q.front();q.pop();
vis[now]=0;
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].y;
if(dis[to]>dis[now]+edge[i].z)
{
dis[to]=dis[now]+edge[i].z;
if(!vis[to])
{
vis[to]=1;
q.push(to);
}
}
}
}
}
void Astar()
{
priority_queue <date> qq;
qq.push((date){e,0,dis[e]});
while(!qq.empty())
{
date nn=qq.top();qq.pop();
++cnt[nn.x];
if(cnt[nn.x]>k)continue;
if(nn.x==s){
ans[++size]=nn.g;
}
if(cnt[s]==k){
return;
}
for(int i=head[nn.x];i;i=edge[i].next)
{
qq.push( (date){edge[i].y,nn.g+edge[i].z,dis[edge[i].y]});
}
}
return;
}
int main()
{
// freopen("cowjog.in ","r",stdin);
// freopen("cowjog.out","w",stdout);
scanf("%d%d%d",&nl,&m,&k);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
if(x<y)swap(x,y);
add(x,y,z);
}
s=1;e=nl;
spfa();
memset(ans,-1,sizeof(ans));
Astar();
for(int i=1;i<=k;i++)
printf("%d\n",ans[i]);
return 0;
}

换了三个A*板子都不对，最后发现spfa出队忘将inqueue清零。。。身败名裂系列。。。。

ctrlC+v上一题，忘记已经改变变量名的尴尬=-=

这图..居然特么还不是连通图..

拓扑不就完了吗。每次保留最小的k个，复杂度O(mk*lgk)

拓扑就A了啊……Yen算法大材小用了吧

这道题专门考察Yen算法，说A*的都被打脸。

第一道A* k短路啊...
感觉有千万头Bessie在我身上践踏...

上课保证好好听..............

A——star！

好费劲的Astar

一开始写的Heap+djistra，然后好像是djistra写错了。。。
后面改成spfa了
还是一道Astar

数据中有陷阱！
注意存图方法。