本文主要是介绍Layout POJ - 3169 （差分约束+SPFA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Layout
题目链接： POJ - 3169题目大意：一条线上站着奶牛， 按1-n编号顺序排列， 两种输入：
ML（i， j， d）表示dis[j]-dis[i]<=d;
MD（i， j， d）表示dis[j]-dis[i]>=d;
求1-n最小距离；
根据差分约束得到 x[i+1]-x[i]>=0;
ML(i, j, d) 得到 i->j=d;(i<j);
MD(i, j, d)得到j->i=d;(i<j);
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int N, ML, MD;
struct node{int v, next;long long w;
}edge[21000];
int head[1100];
int cnt;
void add(int u, int v, long long w){edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;
}
bool vis[1100];
int num[1100];
long long dis[1100];
queue<int> q;
bool SPFA(){for(int i=1; i<=N; i++){if(i==1){q.push(i);num[i]=1;vis[i]=true;dis[i]=0;}else{num[i]=0;vis[i]=false;dis[i]=INF;}}while(!q.empty()){int temp=q.front();q.pop();vis[temp]=false;//cout << temp << endl;for(int i=head[temp]; i!=-1; i=edge[i].next){int to=edge[i].v, w=edge[i].w;if(dis[to]>dis[temp]+w){//cout << to << "---" << endl;dis[to]=dis[temp]+w;if(!vis[to]){vis[to]=true;q.push(to);num[to]++;if(num[to]>N) return false;}}}}return true;
}
int main(){int a, b, t;long long d;scanf("%d%d%d", &N, &ML, &MD);memset(head, -1, sizeof(head));for(int i=0; i<ML; i++){scanf("%d%d%lld", &a, &b, &d);if(a>b){t=a, a=b, b=t;}add(a, b, d);}for(int i=0; i<MD; i++){scanf("%d%d%lld", &a, &b, &d);if(a<b){t=a, a=b, b=t;}add(a, b, -d);}bool flag=SPFA();if(!flag) printf("-1\n");else if(dis[N]==INF) printf("-2\n");else printf("%lld\n", dis[N]);return 0;
}这篇关于Layout POJ - 3169 （差分约束+SPFA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
