本文主要是介绍poj 3169 spfa 差分约束，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给n只牛，这些牛有些关系。
ml个关系：fr 与 to 牛间的距离要小于等于 cost。
md个关系：fr 与 to 牛间的距离要大于等于 cost。
隐含关系： d[ i ] <= d[ i + 1 ]
解析：
用以上关系建图，求1-n间最短路即可。
新学了一种建图的方法。。。。。。
代码：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
#define LL long long
#define lson lo, mi, rt << 1
#define rson mi + 1, hi, rt << 1 | 1using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 1000 + 10;int n, ml, md;struct Edge
{int to, cost;
};
vector<Edge> g[maxn];void spfa(int st, int ed)
{int dis[maxn];int cnt[maxn];bool vis[maxn];memset(dis, inf, sizeof(dis));memset(cnt, 0, sizeof(cnt));memset(vis, false, sizeof(vis));queue<int> q;dis[st] = 0;vis[st] = true;q.push(st);while (!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i = 0; i < g[u].size(); i++){Edge e = g[u][i];int v = e.to;int w = e.cost;if(dis[u] + w < dis[v]){dis[v] = dis[u] + w;if(!vis[v]){if(cnt[v] > n){printf("-1\n");return;}cnt[v]++;q.push(v);vis[v] = true;}}}}if(dis[ed] == inf)printf("-2\n");elseprintf("%d\n", dis[ed]);
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);
#endif // LOCALwhile (~scanf("%d%d%d", &n, &ml, &md)){for (int i = 0; i < ml; i++){int fr, to, cost;scanf("%d%d%d", &fr, &to, &cost); /// d[to] - d[fr] <= costg[fr].push_back({to, cost});}for (int i = 0; i < md; i++){int fr, to, cost;scanf("%d%d%d", &fr, &to, &cost); /// d[fr] - d[to] <= -costg[to].push_back({fr, -cost});}for (int i = 1; i < n; i++){g[i + 1].push_back({i, 0});}spfa(1, n);}return 0;
}
这篇关于poj 3169 spfa 差分约束的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
