[USACO Nov09]找工作

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 jobhunt.in 输出文件 jobhunt.out

问题描述:

贝茜牛身无分文了,她正忙着找工作。农夫约翰知道这个情况,他想让他的牛去周游世界,于是他推行了一个规则:在他的牛到另一个城市工作之前,她们只能在一个城市挣得 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美元。