题解:洛谷 P1260 工程规划

题解:洛谷 P1260 工程规划

前置

需要差分约束和SPFA或BF前置知识，可以在oiwiki上看。

思路

这是一道差分约束的模板题，题目已经告诉了 \(T_i-T_j \le b\) ，直接加边。再设一个超级源点 \(0\) ，连接每个点，跑SPFA就行了，记得判负环。

代码

ll dis[N], st[N], cnt[N];
int n, h;
struct edge{
	int v, w;
};
vector<edge> G[N];
int main(){
	cin>>n>>h;
	memset(dis, inf, sizeof dis);
	for(int i=1;i<=h;i++){
		int u, v, w;
		cin>>u>>v>>w;
		G[v].eb(u, w);
	}
	for(int i=1;i<=n;i++){
		G[0].push_back({i, 0});
	}
	queue<int> q;
	q.push(0);
	dis[0]=0;
	while(!q.empty()){
		int t=q.front();
		q.pop();
		st[t]=0;
		for(auto [v,w]:G[t]){
			if(cmin(dis[v],dis[t]+w)&&!st[v]){
				st[v]=1;
				q.push(v);
				cnt[v]++;
				if(cnt[v]>n){
					cout<<"NO SOLUTION\n";
					return 0;
				}
			}
		}
	}
	int minx=inf;
	for(int i=1;i<=n;i++){
		cmin(minx, dis[i]);
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]-minx<<'\n';
	}
}

本文来自 NoiPLE ，转载请注明原文链接：https://chuna2.787528.xyz/noiple-dequeee/p/19581547