本文主要是介绍World Exhibition（HDU - 3592，差分约束系统），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一.题目链接：
HDU-3592
二.题目大意：
有 n 个人排队，第 i 个人的位置 ≤ 第 i + 1 个人的位置.
有 x 种关系，a b c 表示 a 与 b 之间的距离最大为 c.
有 y 种关系，a b c 表示 a 与 b 之间的距离最小为 c.
求 1 到 n 的最小距离.
若无解，输出 -1.
若可无限大，输出 -2.
否则输出最小距离.
三.分析：
模板题...
之前一直咕掉了，趁着补题学一学.
大佬讲解
四.代码实现：
#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int M = (int)1e3;
const int N = (int)3e4;
const ll inf = 0x3f3f3f3f3f3f3f3f;int cnt;
struct node
{int v, w, nx;
}Edge[N + 5];
int head[M + 5];
bool vis[M + 5];
ll dis[M + 5];int t[M + 5];void init(int n)
{cnt = 0;for(int i = 0; i <= n; ++i){head[i] = -1;vis[i] = 0;dis[i] = inf;t[i] = 0;}
}void add(int u, int v, int w)
{Edge[cnt].v = v;Edge[cnt].w = w;Edge[cnt].nx = head[u];head[u] = cnt++;
}struct cmp
{bool operator()(int a, int b){return dis[a] > dis[b];}
};
priority_queue <int, vector<int>, cmp> q;bool spfa(int s, int n)
{q.push(s);dis[s] = 0, vis[s] = 1, t[s] = 1;while(!q.empty()){int u = q.top();q.pop();vis[u] = 0;for(int i = head[u]; ~i; i = Edge[i].nx){int v = Edge[i].v;if(dis[v] > dis[u] + Edge[i].w){dis[v] = dis[u] + Edge[i].w;if(!vis[v]){vis[v] = 1;q.push(v);t[v]++;if(t[v] > n)return 0;}}}}return 1;
}int main()
{
// freopen("input.txt", "r", stdin);int T;scanf("%d", &T);while(T--){int n, x, y;scanf("%d %d %d", &n, &x, &y);init(n);int a, b, c;while((x--) > 0){scanf("%d %d %d", &a, &b, &c);add(a, b, c);}while((y--) > 0){scanf("%d %d %d", &a, &b, &c);add(b, a, -c);}for(int i = 2; i <= n; ++i)add(i, i - 1, 0);if(!spfa(1, n))printf("-1\n");else if(dis[n] == inf)printf("-2\n");elseprintf("%lld\n", dis[n]);}return 0;
}
这篇关于World Exhibition（HDU - 3592，差分约束系统）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
