分数: 500 点
问题陈述
有 N 城市。 还有连接不同城市的单程直飞航班。
直飞航班的可用性由 N 字符串 S_1,S_2,\ldots,S_N 长度 N 每个。
如果 j- 第一个字符 S_i is Y, 有直飞城市的航班 i 前往城市 j;
如果是的话 N,没有。
每个城市都有卖纪念品;城市 i 出售有价值的纪念品 A_i.
考虑以下问题:
高桥目前在城市 S 想要去市区 T (与城市不同 S) 使用一些直飞航班。
每次他访问一个城市(包括 S 和 T),他在那里买了一件纪念品。
如果有多条从城市出发的路线 S 前往城市 T,高桥决定路线如下:
- 他试图尽量减少从城市出发的航线中的直飞航班数量 S 前往城市 T.
- 然后他尝试最大化他购买的纪念品的总价值。
确定他是否可以从城市出发 S 前往城市 T 使用直达航班。 如果可以的话,找出满足上述条件的航线中的“直飞航班数量”和“纪念品总价值”。
你被给予 Q 对 (U_i,V_i) 不同城市。
对于每个 1\leq i\leq Q,打印上述问题的答案 S=U_i 和 T=V_i.
约束
- 2 \leq N \leq 300
- 1\leq A_i\leq 10^9
- S_i 是一个长度为的字符串 N 组成
Y和N. - 的 i- 第一个字符 S_i is
N. - 1\leq Q\leq N(N-1)
- 1\leq U_i,V_i\leq N
- U_i\neq V_i
- If i \neq j,那么 (U_i,V_i)\neq (U_j,V_J).
- N,A_i,Q,U_i,和 V_i 均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N S_1 S_2 \vdots S_N Q U_1 V_1 U_2 V_2 \vdots U_Q V_Q
输出
打印 Q 行。
的 i-th (1\leq i\leq Q) 行应包含
Impossible 如果他无法从城市出发 U_i 前往城市 V_i;
如果可以的话,该行应按上述顺序包含“直飞航班数量”和“纪念品总价值”,并以空格分隔。
示例输入 1
5 30 50 70 20 60 NYYNN NNYNN NNNYY YNNNN YNNNN 3 1 3 3 1 4 5
示例输出 1
1 100 2 160 3 180
对于 (S,T)=(U_1,V_1)=(1,3), 有直飞城市的航班 1 前往城市 3, 所以直飞航班的最小可能数量是 1,这是当他使用直飞航班时实现的。 在这种情况下,纪念品的总价值是 A_1+A_3=30+70=100.
对于 (S,T)=(U_2,V_2)=(3,1),直飞航班的最小可能数量为 2。 以下两条路线达到最小值: 城市 3\to 4\to 1和城市 3\to 5\to 1。 由于两条路线的纪念品总价值为 70+20+30=120 和 70+60+30=160分别是 所以他选择了后一条路线,纪念品的总价值是 160.
对于 (S,T)=(U_3,V_3)=(4,5),他出行城市时直飞航班最少 4\to 1\to 3\to 5,其中纪念品的总价值为 20+30+70+60=180.
示例输入 2
2 100 100 NN NN 1 1 2
示例输出 2
Impossible
可能根本没有直飞航班。