其实就是spfa 话说看spfa的时候突然发现我原来判负环的板子是锅的然后wa了好几次
就是形如\(x_i-x_j\le k\)的一群问题。我们发现把这个东西移个项之后变成了
\[x_i \le x_j+k \]看着长的就很像最短路。所以就从\(j\)到\(i\)连一条权值为\(k\)的边，用最短路搞吧。特别的，有负环的时候直接判无解。
还有别忘了从0开始向所有点连一个权值0的边。
还有一些长得比较奇怪的，比如\(x_i-x_j\ge k\)这样的。就两边同乘个\(-1\)就成了
\[x_j-x_i\le -k \]这样的了。还有长得像\(x_i-x_j=k\)的。拆成一个\(\le\)一个\(\ge\)就行了。
整个板子吧。就洛谷的板子。
bool spfa(int x){
dis[x]=0;v[x]=true;q.push(x);
while(!q.empty()){
int x=q.front();q.pop();v[x]=false;
for(int i=head[x];i;i=edge[i].next){
if(dis[edge[i].v]>dis[x]+edge[i].w){
dis[edge[i].v]=dis[x]+edge[i].w;
if(!v[edge[i].v]){
v[edge[i].v]=true;q.push(edge[i].v);
cnt[edge[i].v]++;
if(cnt[edge[i].v]>n)return false;
}
}
}
}
return true;
}
int main(){
memset(dis,0x3f,sizeof(dis));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)add(0,i,0);
for(int i=1;i<=m;i++){
int u,v,w;scanf("%d%d%d",&v,&u,&w);
add(u,v,w);
}
if(!spfa(0)){
printf("NO");
return 0;
}
for(int i=1;i<=n;i++)printf("%d ",dis[i]);
return 0;
}