题目描述
奶牛们正在找工作。农场主约翰知道后，鼓励奶牛们四处碰碰运气。而且他还加了一条要求：一头牛在一个城市最多只能赚 \(D\ (1 \le D \le 1000)\) 美元，然后它必须到另一座城市工作。当然，它可以在别处工作一阵子后又回到原来的城市再最多赚 \(D\) 美元。而且这样的往返次数没有限制。
城市间有 \(P\ (1 \le P \le 150)\) 条单向路径连接，共有 \(C\ (1 \le C \le 220)\) 座城市，编号从 \(1\) 到 \(C\)。奶牛贝茜当前处在城市 \(S\ (1 \le S \le C)\)。路径 \(i\) 从城市 \(A_i\) 到城市 \(B_i\)（\(1 \le A_i,B_i \le C\)），在路径上行走不用任何花费。
为了帮助贝茜，约翰让它使用他的私人飞机服务。这项服务有 \(F\ (1 \le F \le 350)\) 条单向航线，每条航线是从城市 \(J_i\) 飞到另一座城市 \(K_i\)（\(1 \le J_i,K_i \le C\)），费用是 \(T_i\ (1 \le T_i \le 50000)\) 美元。如果贝茜手中没有现钱，可以用以后赚的钱来付机票钱。
贝茜可以选择在任何时候，在任何城市退休。如果在工作时间上不做限制，贝茜总共可以赚多少钱呢？如果赚的钱也不会出现限制，就输出 \(-1\)。
输入格式
第一行：\(5\) 个用空格分开的整数 \(D\)，\(P\)，\(C\)，\(F\)，\(S\)。
第 \(2\) 到第 \(P+1\) 行：第 \(i+1\) 行包含 \(2\) 个用空格分开的整数，表示一条从城市 \(A_i\) 到城市 \(B_i\) 的单向路径。
接下来 \(F\) 行，每行 \(3\) 个用空格分开的整数，表示一条从城市 \(J_i\) 到城市 \(K_i\) 的单向航线，费用是 \(T_i\)。
输出格式
一个整数，在上述规则下最多可以赚到的钱数。
输入输出样例 #1
输入 #1
100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120输出 #1
250
说明/提示
这个世界上有五个城市，三条单向路径和两条单向航线。贝茜从一号城市开始她的旅行，她在离开一个城市前最多只能在这个城市赚 \(100\) 美元。
贝茜可以通过从一号城市 \(\to\) 五号城市 \(\to\) 二号城市 \(\to\) 三号城市的旅行赚到 \(4\times 100-150=250\) 美元。
(注：在四个城市各赚 \(100\) 美元，从五号城市飞到二号城市花掉 \(150\) 美元)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 221;
const int MAXQ = 220 * 221 + 10;
const int INF = 1e9;
int D, n, m, F, S;
int Link[MAXN][MAXN], Dist[MAXN], Q[MAXQ], cnt[MAXN];
bool Flg[MAXN];int main() {scanf("%d%d%d%d%d", &D, &n, &m, &F, &S);for (int i = 1; i < m; ++i) for (int j = i + 1; j <= m; ++j) Link[i][j] = Link[j][i] = 1;for (int i = 1; i <= n; ++i) {int a, b; scanf("%d%d", &a, &b);Link[a][b] = 0;}for (int i = 1; i <= F; ++i) {int a, b, c;scanf("%d%d%d", &a, &b, &c);Link[a][b] = -c;}for (int i = 1; i <= m; ++i) Dist[i] = -INF;int f, r; f = 0; r = 1;Q[r] = S; Dist[S] = D; Flg[S] = 1;while (f < r) {int x = Q[++f]; cnt[x]++; Flg[x] = 0;if (cnt[x] == m) {printf("-1"); return 0;}for (int i = 1; i <= m; ++i) {if (x == i) continue;if (Link[x][i] <= 0 && Dist[i] < Dist[x] + Link[x][i] + D) {Dist[i] = Dist[x] + Link[x][i] + D;if (!Flg[i]) Flg[i] = 1, Q[++r] = i;}}}int ans = 0;for (int i = 1; i <= m; ++i) ans = max(ans, Dist[i]);printf("%d", ans);return 0;
}