591. [USACO Nov09] 找工作

问题描述:

贝茜牛身无分文了，她正忙着找工作。农夫约翰知道这个情况，他想让他的牛去周游世界，于是他推行了一个规则：在他的牛到另一个城市工作之前，她们只能在一个城市挣得 D （ 1 <= D <= 1,000 ）美元。不管怎样，贝茜可以在别的城市工作过之后，再返回到某个城市，并在这个城市再挣 D 美元，她可以无限次数地这样做。
贝茜牛的世界包括 P （ 1 <= P <= 150 ）条单向边，这些边连接着 C （ 2 <= C <= 220 ）个城市，城市按 1 到 C 的顺序编号，贝茜牛目前正待在 S 城 (1 <= S <= C) 。单向边 i 从城市 A_i 连到城市 B_i ，其中 1 <= A_i <= C; 1 <= B_i <= C ，在路上不花费任何代价。
为了帮助贝茜，约翰授权它使用他的私人喷气飞机服务。这项服务配置了 F 条航线，每条航线是由城市 J_i 到城市 K_i (1 <=J_i <= C; 1 <= K_i <= C) 的单向航线，且在该航线上的费用是 T_i( 1 <= T_i <= 50,000 ) 美元，如果贝茜牛手头没有现钱，它可以将来挣到钱之后再支付飞行费用。
只要它愿意，贝茜可以随时随地选择退出。不限时间，假定它所有去过的城市都能挣足 D 美元，最后贝茜最多能得到多少钱？如果这个数目没有限制的话输出 -1 。

程序名：jobhunt

输入格式：
第1行：五个空格隔开的整数，D，P，C，F，S；
第2至P+1行：第i行包括两个空格隔开的整数，表示从城市A_i到B_i有一条单向边。
第P+2至P+F+1行：第P+i行包括三个空格隔开的整数，表示从城市J_i到T_i有一条单向航线，费用是T_i。

输入样例：(jobhunt.in):

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

输入样例解释：这个世界有5个城市，三条有向边，和两条飞行航线，贝茜从城市1开始，在每个城市它能最多挣到100美元。

输出格式：
只有一行，一个整数，表示在遵守规则的情况下，它最多能得到多少钱。

输出样例：(jobhunt.out):

250
输出样例解释：贝茜能从城市1→城市5→城市2→城市3，最后共得到4*100 - 150 = 250美元。