洛谷P5960 【模板】差分约束算法

传送门

当年崔叔就讲得这个东西,感觉把不等式转化成最短路这个想法就很神奇,今天又回来温习了一下(累了懒得解释了,过几天来补 咕咕咕

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int M=20005;
const int N=5005;
int n,m,tot,head[M],to[M],nex[M],v[M],num[N],dis[N];
bool vis[N];
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
inline void add(int x,int y,int z){
   
	++tot;
	nex[tot]=head[x];
	head[x]=tot;
	to[tot]=y;
	v[tot]=z;
}
inline bool spfa(int s){
   
	queue<int>q;
	q.push(s);
	for(int i=1;i<=n;i++) vis[i]=0;
	vis[s]=1,dis[s]=0;
	while(!q.empty()){
   
		int dmf=q.front();
		q.pop();	
		for(int i=head[dmf];i;i=nex[i]){
   
			int lgr=to[i];
			if(dis[lgr]>dis[dmf]+v[i]){
   
				dis[lgr]=dis[dmf]+v[i];
				if(!vis[lgr]){
   
					vis[lgr]=1;
					num[lgr]++;
					
					if(num[lgr]>=n) return 0;
					q.push(lgr);
				}
			}
		} 
		vis[dmf]=0;
	}
	return 1;
}
int main(){
   
	n=read();m=read();
	for(int i=1;i<=n;i++) add(0,i,0),dis[i]=2147483640,num[i]=0;
	for(int i=1;i<=m;i++){
   
		int x,y,z;
		x=read();y=read();z=read(); 
	    add(y,x,z);
	}
	if(spfa(0)){
   
		for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	}
	else printf("NO");
	return 0;
} 
全部评论

相关推荐

点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 12:31
以前小时候我最痛恨出轨、偷情的人,无论男女,为什么会出轨?现在我成了自己最讨厌的人,没想到分享的东西在牛客会被这么多人看,大家的评价都很中肯,我也认同,想过一一回复,但我还是收声了,我想我应该说说这件事,这件事一直压在我心里,是个很大的心结,上面说了人为什么出轨,我大概能明白了。我们大一下半年开始恋爱,开始恋爱,我给出了我铭记3年的承诺,我对她好一辈子,我永远不会背叛,我责任心太重,我觉得跟了我,我就要照顾她一辈子,我们在一起3年我都没有碰过她,她说往东我就往东,她说什么我做什么,她要我干什么,我就干什么!在学校很美好,中途也出过一些小插曲,比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了,我...
牛客刘北:两个缺爱的人是没有办法好好在一起的,但世界上哪有什么是非对错?你后悔你们在一起了,但是刚刚在一起的美好也是真的呀,因为其他人的出现,你开始想要了最开始的自己,你的确对不起自己,21岁的你望高物远,你完全可以不谈恋爱,去过你想要的生活,你向往自由,在一起之后,你要想的不是一个人,而是两个人,你不是变心了,就像你说的,你受够了,你不想包容了,冷静几天是你最优的选择,爱人先爱己。
社会教会你的第一课
点赞 评论 收藏
分享
昨天 12:17
已编辑
商丘师范学院 Java
后来123321:别着急,我学院本大二,投了1100份,两个面试,其中一个还是我去线下招聘会投的简历,有时候这东西也得看运气
无实习如何秋招上岸
点赞 评论 收藏
分享
机械打工仔:我来告诉你原因,是因为sobb有在线简历,有些HR为了快会直接先看在线简历,初步感觉不合适就不会找你要详细的了
投了多少份简历才上岸
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务