题意:有两种关系,n牛按照序号排列,A1到B1的距离不超过C1, A2到B2的距离不小于C2,问1到n的距离最大是多少.如果无限的话是-2, 如果无解是-1
分析:第一种可以写这样的方程:d[v] - d[u] <= w1, u到v连一条权值为w1的边,第二种这样:d[v] - d[u] >= w2 => d[u] - d[v] <= -w2,v到u连一条-w2的边.当然根据题目还有i+1 到 i连权值0的边.最短路就是为了d[v] <= d[u] + w[u][v], 也就是d[v] - d[u] <= ans.求出最短路也就是满足了所有方程的约束条件.如果INF无解,如果负环无数解,否则就是ans了.
//#include <bits/stdc++.h> #include <cstdio> #include <algorithm> #include <cstring> #include <queue> using namespace std; const int N = 1e3 + 5; const int E = 2e4 + 5; const int INF = 0x3f3f3f3f; struct Edge { int v, w, nex; Edge() {} Edge(int v, int w, int nex) : v (v), w (w), nex (nex) {} }edge[E*2]; int head[N]; int d[N]; bool vis[N]; int cnt[N]; int n, m1, m2, e; void init(void) { memset (head, -1, sizeof (head)); e = 0; } void add_edge(int u, int v, int w) { edge[e] = Edge (v, w, head[u]); head[u] = e++; } bool SPFA(int s) { memset (vis, false, sizeof (vis)); memset (cnt, 0, sizeof (cnt)); memset (d, INF, sizeof (d)); d[s] = 0; cnt[s] = 0; vis[s] = true; queue<int> que; que.push (s); while (!que.empty ()) { int u = que.front (); que.pop (); vis[u] = false; for (int i=head[u]; ~i; i=edge[i].nex) { int v = edge[i].v, w = edge[i].w; if (d[v] > d[u] + w) { d[v] = d[u] + w; if (!vis[v]) { vis[v] = false; que.push (v); if (++cnt[v] > n) return true; } } } } return false; } int main(void) { while (scanf ("%d%d%d", &n, &m1, &m2) == 3) { init (); for (int i=1; i<n; ++i) { add_edge (i+1, i, 0); } for (int u, v, w, i=1; i<=m1; ++i) { scanf ("%d%d%d", &u, &v, &w); add_edge (u, v, w); } for (int u, v, w, i=1; i<=m2; ++i) { scanf ("%d%d%d", &u, &v, &w); add_edge (v, u, -w); } if (SPFA (1)) puts ("-1"); else { bool ok = true; for (int i=1; i<=n; ++i) { if (d[i] == INF) { ok = false; break; } } if (!ok) puts ("-2"); else printf ("%d ", d[n]); } } return 0; }