WA on #3 但是输出了2^31-1
查看原帖
WA on #3 但是输出了2^31-1
1125069
Silver_winter楼主2025/7/30 11:59

下载了一下#3,除了输出23112^{31}-1的部分,其它也有错

#include<bits/stdc++.h>
using namespace std;
long long n,m,s;
struct ss{
	long long next,val;
};
vector<ss>E[1000005];
queue<long long>Q;
long long a[10000005];
long long x,y,z,f;
long long minn,nid;
long long c[10000005];
int main(){
	cin>>n>>m>>s;
	for(long long i=1;i<=m;i++){
		cin>>x>>y>>z;
		E[x].push_back({y,z});
	}
	memset(a,0x7f,sizeof(a));
	a[s]=0;
	c[s]=1;
	Q.push(s);
	while(!Q.empty()){
		//cout<<f<<endl;
		minn=0x7f;
		f=Q.front();
		Q.pop();
		for(long long i=0;i<E[f].size();i++){
			a[E[f][i].next]=min(a[f]+E[f][i].val,a[E[f][i].next]);
		}
		for(long long i=1;i<=n;i++){
			if(a[i]<minn&&!c[i]){
				minn=a[i];
				nid=i;
			}
		}
		if(!c[nid])Q.push(nid);
		c[nid]=1;
	}
	for(long long i=1;i<=n;i++){
		if(a[i]==0x7f)cout<<2147483647<<" ";
		else cout<<a[i]<<" ";
		
	}
	return 0;
}
2025/7/30 11:59
加载中...