问题 3560 --货物交易

3560: 货物交易

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

哥伦布要从野人手里买n种货物,如果货物要包装则还得多付1金。可以用以下几种方法买到货物:
1.按货物的价格付足金币。
2.付一个玻璃珠和一些金币(因为野人对玻璃珠很好奇,可以用来抵付一个金币)。就是说如果某以货物需要k金币,哥伦布只要付k-1个金币和一个玻璃珠就行。(哥伦布很庆幸自己有的是玻璃!)
3.用等价格的其他种类货物交换。
4.用价格更低的货物加上金币来交换。在这种价格不等的物物交换中,某些低价价格的货物可以置换某些高价价格的货物,这些低价价格的货物置换某些高价价格的货物时,要补足的金币数量比两者的价格差要小。
哥伦布想知道每种货物实际至少要花多少金币才能买到。也想知道有多少种货物的实际最少价格是其他两种货物的实际最少价格之和。

 

输入

第一行一个整数n,表示货物的总数。(0 < n <= 100)
接下来n行,每行两个整数q、p,表示第q种货物需要金币p个。(0 < p <= 150)
再下一行一个整数m,表示还有m种物物交换形式。(0 < m <= 100)
下面的m行,每行三个整数n1、n2、r,表示你可以买到第n2种货物用第n1种货物加上r个金币来换取。注意r值可以是0。

 

输出

先输出n行,第i行包括两个整数i,ci。表示第i种实际最少换购价。两数用一个空格隔开
再一行输出有多少种货物的实际最少价格是其他两种货物的实际最少价格之和。

样例输入

4
1 4
2 9
3 5
4 13
2
1 2 3
3 4 6

样例输出

1 3
2 6
3 4
4 10
1

提示

题目源:PKU 3835

来源

 

[提交][状态]