求助 dij #7 #8 WA
查看原帖
求助 dij #7 #8 WA
432183
JoeBiden2020楼主2021/12/25 18:54

错误地输出了-1?

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=300005,maxm=300005;
struct Edge{
	int u,v,w,next;
} e[maxm];
int h[maxn],cnt,n,m,s,vis[maxn],dis[maxn],x,y,z;
struct node{
	int w,now;
	bool operator <(const node &x)const{
		return w>x.w;
	}
};
priority_queue<node>q;
inline void add(int u,int v,int w) {
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=h[u];
	h[u]=cnt;
}
void dij() {
	for(int i=1;i<=n;i++){
		dis[i]=1e18;
	}
	dis[s]=0;
	q.push((node){0,s});
	while(!q.empty()){
		node x=q.top();
		q.pop();
		int u=x.now;
		if(vis[u])continue;
		vis[u]=1;
		for(int i=h[u];i!=0;i=e[i].next){
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w) {
				dis[v]=dis[u]+e[i].w;
				q.push((node){dis[v],v});
			}
		}
	}
}
signed main() {
	cin>>n>>m;s=1;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		add(x,y,z);
	}
	dij();
	for(int i=1;i<=n;i++){
		if(dis[i]!=1e18)printf("%d ",dis[i]);
		else printf("-1 ");
	}
	return 0;
}
2021/12/25 18:54
加载中...