题目链接:http://poj.org/problem?id=3169
题意:n头牛编号为1到n,按照编号的顺序排成一列,每两头牛的之间的距离 >= 0。这些牛的距离存在着一些约束关系:1.有ml组(u, v, w)的约束关系,表示牛[u]和牛[v]之间的距离必须 <= w。2.有md组(u, v, w)的约束关系,表示牛[u]和牛[v]之间的距离必须 >= w。问如果这n头无法排成队伍,则输出-1,如果牛[1]和牛[n]的距离可以无限远,则输出-2,否则则输出牛[1]和牛[n]之间的最大距离
很明显的差分约束整理一下条件,这些点是按顺序排的。
1.dis[B]-dis[A]<=D1;
2.dis[B]-dis[A]>=D2;
3.dis[B]>=dis[A];
由1得dis[B]<=dis[A]+D1--->dis[B]>dis[A]+D1的最短路条件
由2得dis[A]<=dis[B]+(-D2)--->dis[A]>dis[B]+(-D2)的最短路条件
然后只要判断一下,如果有负环则永远无法到,如果dis[n]=inf那么1~n的距离就可以任意,
否则就是输出dis[n]即可
#include <iostream> #include <cstring> #include <string> #include <cstdio> #include <queue> #define inf 0X3f3f3f3f using namespace std; int n , ml , md , a , b , d , dis[1010] , cnt[1010]; struct TnT { int v , next , w; }Edge[3000010]; int head[1010] , e; void init() { e = 0; for(int i = 1 ; i <= n ; i++) { head[i] = -1; } } void add(int u , int v , int w) { Edge[e].v = v; Edge[e].w = w; Edge[e].next = head[u]; head[u] = e++; } bool vis[1010]; bool spfa(int sta) { memset(vis , false , sizeof(vis)); memset(cnt , 0 , sizeof(cnt)); queue<int>q; q.push(sta); vis[sta] = true; dis[sta] = 0; cnt[sta]++; while(!q.empty()) { int u = q.front(); vis[u] = false; q.pop(); for(int i = head[u] ; i != -1 ; i = Edge[i].next) { int v = Edge[i].v , w = Edge[i].w; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; if(!vis[v]) { vis[v] = true; cnt[v]++; q.push(v); if(cnt[v] > n) return false; } } } } return true; } int main() { scanf("%d%d%d" , &n , &ml , &md); init(); for(int i = 1 ; i <= n ; i++) { dis[i] = inf; } for(int i = 1 ; i <= ml ; i++) { scanf("%d%d%d" , &a , &b , &d); add(min(a , b) , max(a , b) , d); } for(int i = 1 ; i <= md ; i++) { scanf("%d%d%d" , &a , &b , &d); add(max(a , b) , min(a , b) , -d); } int flag = spfa(1); if(flag) { if(dis[n] == inf) { printf("-2 "); } else { printf("%d " , dis[n]); } } else { printf("-1 "); } return 0; }