#P3482. [COCI2013]hiperprostor

    ID: 2694 传统题 1500ms 512MiB 尝试: 533 已通过: 123 难度: 7 上传者: 标签>难度分类提高+/省选-图论分层图Dijkstra数论向下取整与向上取整线性代数与代数等差数列求和CF2300ByHta

[COCI2013]hiperprostor

HIPERPROSTOR

题目描述

在遥远的未来,商人通过单向航线在行星间运送食物。每条常规航线直接连接两颗行星,耗时已知。商会准备新增一些单向超空间航线。超空间航线的耗时与行星间的距离无关,所有这类航线都耗时 xx 天。xx 尚未确定,可以取任意正整数。

对每组给出的行星 A,BA,B,考虑 xx 的所有可能取值。对于每个 xx,计算从 AA 到 BB 的最短总耗时。求这些最短耗时中有多少个不同的值,以及它们的总和。

下图对应第二组样例。从行星 22 到行星 11 的最短耗时为 min⁡(x,5)\min(x,5),因此可能的值是 1,2,3,4,51,2,3,4,5 天。

样例二中的三颗行星与五条有向航线

输入格式

第一行包含两个整数 P,RP,R,分别表示行星数和航线数。

接下来 RR 行,每行给出 C,D,TC,D,T,表示一条从 CC 到 DD 的航线。常规航线的 TT 为一个正整数,表示耗时天数。超空间航线的 TT 为字符 x。相同行星之间可以有多条航线。

接下来一行包含整数 QQ,表示询问数。之后 QQ 行,每行两个整数 A,BA,B,表示起点和终点。

输出格式

每条询问输出一行。如果 AA 无法到达 BB,输出 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

样例一中的四颗行星与四条有向航线

行星 22 无法到达行星 11。从行星 11 到行星 33 的最短耗时始终为 2x2x 天。从行星 11 到行星 44 的最短耗时为 min⁡(3x,8)\min(3x,8) 天,可能的值为 3,6,83,6,8,总和为 1717。

样例 #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

数据范围

1≤P≤5001\le P\le 500,0≤R≤10 0000\le R\le 10\,000,1≤Q≤101\le Q\le 10。

1≤C,D,A,B≤P1\le C,D,A,B\le P,C≠DC\ne D,A≠BA\ne B。每条常规航线满足 1≤T≤1061\le T\le 10^6。

原赛中,共 5050 分的数据满足 P≤30P\le 30、R≤300R\le 300、常规航线的 T≤50T\le 50。原赛还为每行个数均正确、但总和有误的结果保留该测试一半的分值,有限值的答案每行仍须输出两个整数。本题归档按现有配置逐项比较完整答案。