谁来九九我,错4个点
查看原帖
谁来九九我,错4个点
546282
bianxingyu1111楼主2023/5/10 21:11
#include<iostream>
#include<vector> 
using namespace std;
struct Edge{
	int v,w;
	Edge(){}
	Edge(int a,int b):v(a),w(b){}
};
int n,m,s,dis[5005];
vector<Edge> edge[5005];
bool inStk[5005],HNR,vis[5005];
void spfa_dfs(int u){
	if(HNR)
		return;
	inStk[u]=true;
	for(Edge e:edge[u]){
		if(HNR)
			return;
		int v=e.v,w=e.w;
		if(dis[v]>dis[u]+w){
			dis[v]=dis[u]+w;
			if(inStk[v]==true){
				HNR=true;
				return;
			}
			spfa_dfs(v);
		}
	}
	inStk[u]=false;
}
void dfs(int u){
	vis[u]=1;
	for(Edge e:edge[u]){
		int v=e.v;
		if(vis[v]==false){
			vis[v]=true;
			dfs(v);
		}
	}
}
int main(){
	int t,a,b,c;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>t;
		if(t==1){
			cin>>a>>b>>c;
			edge[a].push_back(Edge(b,-c));
		}
		else if(t==2){
			cin>>a>>b>>c;
			edge[b].push_back(Edge(a,c));
		}
		else{
			cin>>a>>b;
			edge[a].push_back(Edge(b,0));
			edge[b].push_back(Edge(a,0));
		}
	} 
	dfs(1);
	for(int v=1;v<=n;v++)
		if(vis[v])
			spfa_dfs(v);
	if(HNR)
		cout<<"No"<<endl;
	else
		cout<<"Yes"<<endl;
	return 0;
}
2023/5/10 21:11
加载中...