当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2249:最小费用狗

题目描述
在地球上的一个鲜为人知的角落,住着这样一群人.他们整日与算法为伴,以研究出高效的算法为荣.就连竞选村长都是以Word Final的标准进行的.这里的算法风气之浓厚,就连当地的动物们都受到了极大的影响.旺财是村长--TCL(相当于世界冠军的水平)的爱犬,从小就受到村长一家的熏陶,当别的小动物都还在算A+B的的时候,旺财已经学会"迪杰斯特拉"和"贝尔曼-佛德"了,因此他一直是当地的小动物们崇拜的对象,它们眼中的最有希望进Animal Kingdom World Final的明日之星,就连村里面耕地的老牛们见了他都要叫声"大牛好~".
可是,旺财也有他的苦衷.TCL对待他实在是太好了,每天都请医疗专家周海角为旺财开出许多的保健药品(据说TCL那么牛就是因为从小吃周海角开的药).周海角作为一名医疗专家,有着数十年的江湖行医经验,他的药方不是一般人能开得出来的.他每次都会开出两张药方,第一张药方上写有N1种药品(每种药的编号分别为1,2,3……,N1),第二张药方上写有N2种药品(编号分别为N1+1,N1+2,N1+3……,N1+N2),之所以要这样,是因为第一张药方上的药只有村北的药店里才有,而第二张药方上的药只有村南的药店里才有,并且,药方上还明确指出哪些药必须在哪些药服用之后才能服用,否则会有脑残的危险!还需要一提的药是不能打包带回去,只能在相应的药店里在专家指导下当场服用,安全第一嘛。旺财还面临的一个问题是:村北和村南的药店相隔甚远,而且两地之间还有一个规定凡是4条腿或4个轮子的东西经过都要交钱的收费站,作为一条精通算法的小狗,旺财始终把"提高效率减小耗费"作为自己的座右铭.他在想要怎样吃药才能使跑远路的次数最少,这样过路费也会最小.从村南到村北或从村北到村南算一次跑远路,到最后吃完药跑回家,也算一次哦.
输入解释
有多组输入数据.每组数组的第一行有三个整数N1, N2, M. 接下来有M行数组,每行有两个整数 a, b, 分别表示在吃第a种药之前,需要先吃第b种药. 最后一组数据后,会有三个0表示输入结束。所有的数据中, 1<=N1,N2<=60000, 0<=M<=120000, 1<=a,b<=N1+N2.
输出解释
每组数据输出一个整数,表示旺财把药房上的药吃完所需的跑远路的次数.
输入样例
5 3 3
1 2
5 1
3 2
0 0 0
输出样例
3
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-2249

最后修改于 2020-10-25T22:51:51+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
1000/1000MS(Java/Others) 32768/32768K(Java/Others)