这两题完全一个意思,都是差分约束的水题
找到约束条件然后建边求最短路即可
#include <map> #include <set> #include <list> #include <stack> #include <vector> #include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1010; const int M = 20010; const int inf = 0x3f3f3f3f; queue <int>qu; int tot, n, m; int head[N]; int num[N]; int dist[N]; int in_queue[N]; struct node { int weight; int next; int to; }edge[M]; void addedge(int from, int to, int weight) { edge[tot].weight = weight; edge[tot].to = to; edge[tot].next = head[from]; head[from] = tot++; } bool spfa(int v0) { memset (dist, inf, sizeof(dist) ); memset (in_queue, 0, sizeof(in_queue) ); dist[v0] = 0; in_queue[v0]++; while ( !qu.empty() ) { qu.pop(); } qu.push(v0); while ( !qu.empty() ) { int u = qu.front(); qu.pop(); for (int i = head[u]; ~i; i = edge[i].next) { int v = edge[i].to; if (dist[v] > dist[u] + edge[i].weight) { dist[v] = dist[u] + edge[i].weight; in_queue[v]++; if (in_queue[v] == n + 1) { return false; } qu.push(v); } } } return true; } int main() { int m1, m2; int t; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &m1, &m2); memset (head, -1, sizeof(head) ); tot = 0; int u, v, w; while (m1--) { scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); } while (m2--) { scanf("%d%d%d", &u, &v, &w); addedge(v, u, -w); } for (int i = 1; i <= n; ++i) { addedge(i + 1, i, 0); } bool flag = spfa(1); if (!flag) { printf("-1\n"); continue; } for (int i = 1; i <= n; ++i) { if (dist[i] != inf) { continue; } flag = false; break; } if (!flag) { printf("-2\n"); continue; } printf("%d\n", dist[n]); } return 0; }