看我的dij里面有几处错啊,它A了这题
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
const int N=1005,M=10005;
int n,m,k;
int cnt=1,head[N],head2[N],cnt2=1,dis[N];
struct aa{
int u,v,w,next;
}f[M],f2[M];
struct node{
int u,f,g;
bool operator < (const node &p)const{
return f>p.f;
}
};
void adde(int u,int v,int w){
f[cnt].u=u;f[cnt].v=v;
f[cnt].w=w;f[cnt].next=head[u];
head[u]=cnt++;
}
void Adde(int u,int v,int w){
f2[cnt2].u=u;f2[cnt2].v=v;
f2[cnt2].w=w;f2[cnt2].next=head2[u];
head2[u]=cnt2++;
}
void dijkstra(int s){
priority_queue <pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;//<dis,u>
int vis[N],u,d;memset(vis,0,sizeof(vis));
q.push(make_pair(0,s));vis[s]=1;dis[s]=0;
while(!q.empty()){
u=q.top().second,d=q.top().first;q.pop();
if(vis[u]) continue;
for(int i=head2[u],v,w;i!=-1;i=f2[i].next){
v=f2[i].v;w=f2[i].w;
if(dis[s]+w<dis[v]){
dis[v]=dis[s]+w;
if(!vis[v]) q.push(make_pair(dis[v],v));
}
}
}
}
void astar(int k){
int tot=0;
priority_queue <node> q;
q.push((node){n,0,dis[n]});
while(!q.empty()){
node p=q.top();q.pop();
if(p.u==1){
cout<<p.f<<'\n';
if(++tot==k) return;
continue;
}
for(int i=head[p.u],v,w;i!=-1;i=f[i].next){
v=f[i].v;w=f[i].w;
q.push((node){v,p.g+w,p.g+w+dis[v]});
}
}
cout<<-1;
}
int main(){
cin>>n>>m>>k;
memset(head,-1,sizeof(head));
memset(head2,-1,sizeof(head2));
for(int i=1,u,v,w;i<=m;i++){
cin>>u>>v>>w;
adde(u,v,w);
Adde(v,u,w);
}cnt--;
dijkstra(n);
astar(k);
return 0;
}