A了,但是为什么
查看原帖
A了,但是为什么
951050
lostxxx楼主2024/10/16 11:52

虽然过了,但是样例没过,能不能帮我找出代码里的问题,谢谢。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll head[200100],to[200100],nxt[200100];
ll w[200100],cnt=-1;
bool vis[200100];
ll dis[200100],tot[200100];
void add(ll u,ll v,ll co){
	nxt[++cnt]=head[u];
	head[u]=cnt;
	to[cnt]=v;
	w[cnt]=co;
}
ll opt,a,b,c;
queue<ll>q;
bool spfa(){
	memset(dis,0x3f,sizeof(dis));
	vis[0]=1;
	q.push(0);
	dis[0]=0;
	while(q.size()){
		ll u=q.front();
		q.pop();
		vis[u]=0;
		for (int i=head[u];~i;i=nxt[i]){
			ll v=to[i],co=w[i];
			if (dis[v]>dis[u]+co){
				dis[v]=dis[u]+co;
				tot[v]=tot[u]+1;
				if (tot[v]>=n)
					return 1;
				if (!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return 0;
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		cin>>opt;
		if (opt==1){
			cin>>a>>b>>c;
			add(b,a,-c);
		}else if (opt==2){
			cin>>a>>b>>c;
			add(a,b,c);
		}else{
			cin>>a>>b;
			add(a,b,0);
			add(b,a,0);
		}
	}
	for (int i=1;i<=n;i++)
		add(0,i,0);
	if (spfa())
		cout<<"No";
	else
		cout<<"Yes";
}
2024/10/16 11:52
加载中...