spfa板子

判负环,求带负权边的最短路。

#include<stdio.h>
#include<vector>
#include<queue>
#include<cstring>
const int inf=0x3f3f3f3f;
using namespace std;
struct node{
   
	int a,b;
	node(int _a,int _b):a(_a),b(_b){
   
	}
};
vector<node> v[1000];
int n,d[1000],m,w,num[1000];
bool vis[1000];
bool spfa(){
   
	queue<int> q;
	q.push(1);
	vis[1]=true;
	num[1]++;
	d[1]=0;
	while(!q.empty()){
   
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int j=0;j<v[u].size();j++){
   
			int t=v[u][j].a;
			int tt=v[u][j].b;
			if(d[u]+tt<d[t]){
   
				d[t]=d[u]+tt;
				if(!vis[t])
				q.push(t);
				vis[t]=true;
				num[t]++;
				if(num[t]>=n)	return true;
			}
		}
	}
	return false;
}
void init(){
   
	for(int i=0;i<1000;i++)
		v[i].clear();
	memset(num,0,sizeof(num));
	memset(vis,0,sizeof(vis));
	fill(d,d+1000,inf);
}
int main(){
   
	int t;
	scanf("%d",&t);
	while(t--){
   
		init();
		scanf("%d%d%d",&n,&m,&w);
		for(int i=0;i<m;i++){
   
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			v[x].push_back(node(y,z));
			v[y].push_back(node(x,z));
		}
		for(int i=0;i<w;i++){
   
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			v[x].push_back(node(y,-z));
		}
		if(spfa())	printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
全部评论

相关推荐

1.&nbsp;事件概述3月10日下午,华为在“心声社区”发布长达6500字通报,曝光72名正式员工及19名非雇员在非雇员招聘中存在徇私舞弊行为,多人出卖公司信息资产获利,引发热议。-&nbsp;“非雇员”一般指华为OD员工,与人力服务公司签劳动合同,以派遣方式到华为工作,薪资待遇与华为内部员工基本一致,可通过考核转正。2.&nbsp;相关传言与真相华为相关人士称暂无官方回应,很多传言细节不准确。&nbsp;华为成都研究所员工透露,此次通报主要涉及成都研究所的数据存储部门,整个数据存储业务约100余人,此次明文通报除名辞退或通报批评的有62名,“很多部门基本全开除”&nbsp;。网传任正非亲赴成都、封楼抓人等消息不实。早在2024年年中,就有...
七安有出处嘛:省流:任正非亲赴成都等消息不实,2024 年年中就有人举报了;涉及36名违规当事人,其中有13人被除名;10人有主动申报情节或情节较严重的,予以辞退处理;另有13人被劝退、个人职级降3等。另外还有26名相关管理责任人作为直接或间接管理者,被处以个人职级降6等,冻结个人涨薪、职级晋升、干部向上任命,冻结期6—12个月不等;若下属违规偶发,则仅通报批评。并没有释放100HC😂😂😂
点赞 评论 收藏
分享
vip牛牛:测试吧,开发现在至少212
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务