洛谷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;
} 

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议