#P3482. [COCI2013]hiperprostor
[COCI2013]hiperprostor
HIPERPROSTOR
题目描述
在遥远的未来,商人通过单向航线在行星间运送食物。每条常规航线直接连接两颗行星,耗时已知。商会准备新增一些单向超空间航线。超空间航线的耗时与行星间的距离无关,所有这类航线都耗时 天。 尚未确定,可以取任意正整数。
对每组给出的行星 ,考虑 的所有可能取值。对于每个 ,计算从 到 的最短总耗时。求这些最短耗时中有多少个不同的值,以及它们的总和。
下图对应第二组样例。从行星 到行星 的最短耗时为 ,因此可能的值是 天。

输入格式
第一行包含两个整数 ,分别表示行星数和航线数。
接下来 行,每行给出 ,表示一条从 到 的航线。常规航线的 为一个正整数,表示耗时天数。超空间航线的 为字符 x。相同行星之间可以有多条航线。
接下来一行包含整数 ,表示询问数。之后 行,每行两个整数 ,表示起点和终点。
输出格式
每条询问输出一行。如果 无法到达 ,输出 0 0。如果不同最短耗时有无穷多个,输出 inf。否则输出两个整数,依次为不同最短耗时的个数与它们的总和。
样例 #1
4 4
1 2 x
2 3 x
3 4 x
1 4 8
3
2 1
1 3
1 4
0 0
inf
3 17

行星 无法到达行星 。从行星 到行星 的最短耗时始终为 天。从行星 到行星 的最短耗时为 天,可能的值为 ,总和为 。
样例 #2
3 5
3 2 x
2 1 x
2 1 5
1 3 10
3 1 20
6
1 2
2 3
3 1
2 1
3 2
1 3
inf
5 65
15 185
5 15
inf
1 10
数据范围
,,。
,,。每条常规航线满足 。
原赛中,共 分的数据满足 、、常规航线的 。原赛还为每行个数均正确、但总和有误的结果保留该测试一半的分值,有限值的答案每行仍须输出两个整数。本题归档按现有配置逐项比较完整答案。