← 返回题目列表

AtCoder · abc286_e

H. 纪念品

中文机器翻译题面 查看原题

分数: 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

可能根本没有直飞航班。