求加强数据(太水了)
查看原帖
求加强数据(太水了)
531499
windows_fleon楼主2022/11/18 15:42

看我的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;
}
2022/11/18 15:42
加载中...