[USACO09NOV] Job Hunt S

题目描述

Bessie 正在找工作，因为她快要没钱了。农场主 John 知道了这一情况，并希望奶牛们在各个城市之间旅行工作。因此，他规定奶牛们在每座城市最多只能赚取 $D$ 美元（$1 \leq D \leq 1000$），之后必须去别的城市工作。不过，Bessie 可以在别的城市工作一段时间后，再次回到之前的城市，并且可以再次赚取最高 $D$ 美元。在城市之间的往返次数没有限制。

Bessie 所在的世界有 $P$ 条单向路径（$1 \leq P \leq 150$）连接着 $C$ 座城市（$2 \leq C \leq 220$），城市编号从 $1$ 到 $C$。Bessie 当前位于城市 $S$（$1 \leq S \leq C$）。路径 $i$ 是从城市 $A_i$ 到城市 $B_i$ 的单向路径（$1 \leq A_i \leq C$；$1 \leq B_i \leq C$），在这条路径上行走不需要任何费用。

为了帮助 Bessie，农场主 John 提供了一项私人飞机服务。这项服务有 $F$ 条航线（$1 \leq F \leq 350$），每条航线是从城市 $J_i$ 飞到城市 $K_i$（$1 \leq J_i \leq C$；$1 \leq K_i \leq C$），每条航线的费用为 $T_i$ 美元（$1 \leq T_i \leq 50000$）。如果 Bessie 手头没有足够的现金，她可以从未来的收入中支付这些机票费用。

Bessie 可以在任何时候选择退休，不受时间限制。你需要计算 Bessie 能赚取的最多金额，假设她可以在每座城市赚取全额 $D$ 美元。如果 Bessie 的收入没有上限，输出 $-1$。

输入格式

第一行输入 5 个空格分隔的整数：$D$，$P$，$C$，$F$，$S$。

接下来的 $P$ 行，每行包含 2 个空格分隔的整数，表示从城市 $A_i$ 到城市 $B_i$ 的一条单向路径。

接下来的 $F$ 行，每行包含 3 个空格分隔的整数，表示一条从城市 $J_i$ 到城市 $K_i$ 的单向航线，费用为 $T_i$ 美元。

输出格式

输出一个整数，表示在上述规则下 Bessie 能够赚取的最多金额。如果 Bessie 可以赚取无限多的钱，输出 $-1$。

样例 #1

样例输入 #1

100 3 5 2 1
1 5
2 3
1 4
5 2 150
2 5 120

样例输出 #1

250

提示

这个世界包含 5 座城市，3 条单向路径和 2 条航线。Bessie 从城市 $1$ 开始旅行，每座城市她最多可以赚取 $100$ 美元。

Bessie 可以从城市 $1$ 旅行到城市 $5$，再到城市 $2$，然后到城市 $3$。她可以赚取总共 $4 \times 100 - 150 = 250$ 美元。

题目来源

来源：USACO 2009 年 11 月 银组