网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[USACO Nov09]找工作
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23: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美元。