求助,50pts,真的找不出哪有问题了QAQ
查看原帖
求助,50pts,真的找不出哪有问题了QAQ
356081
Night_7d5楼主2021/9/24 20:45
#include<bits/stdc++.h>
#define N 5004
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
struct edge {
	int to,next,w;
}e[N<<4];
int head[N],cnt;
void add(int u,int v,int w) {
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	head[u]=cnt;
}
void input() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		add(0,i,0);
	}
	for(int i=1,opt,a,b,c;i<=m;i++) {
		scanf("%d",&opt);
		if(opt==1) {
			scanf("%d%d%d",&a,&b,&c);
			add(b,a,-c);
		}
		if(opt==2) {
			scanf("%d%d%d",&a,&b,&c);
			add(b,a,c);
		}
		if(opt==3) {
			scanf("%d%d",&a,&b);
			add(b,a,0);
			add(a,b,0);
		}
	}
}
int dis[N],vis[N],Count[N];
bool SPFA(int s) {
	queue<int> q;
	memset(dis,INF,sizeof(dis));
	q.push(s);
	Count[s]++;
	dis[s]=0;
	vis[s]=1;
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].next) {
			int v=e[i].to;
			if(dis[v]>dis[u]+e[i].w) {
				dis[v]=dis[u]+e[i].w;
				if(!vis[v]) {
					vis[v]=1;
					q.push(v);
					Count[v]++;
					if(Count[v]>n) return false;
				}
			}
		}
	}
	return true;
}
int main() {
	freopen("stdin.in","r",stdin);
	input();
	if(SPFA(0)) printf("Yes");
	else printf("No");
	return 0;
}
2021/9/24 20:45
加载中...