Souvenir

题目描述

有 $N$ 个城市。城市之间也有单向的直达航班连接。
直达航班的有无由 $N$ 个长度为 $N$ 的字符串 $S_1,S_2,\ldots,S_N$ 表示。 如果 $S_i$ 的第 $j$ 个字符是 $Y$，则存在从城市 $i$ 到城市 $j$ 的直达航班； 如果是 $N$，则不存在。
每个城市都出售一个纪念品；城市 $i$ 出售价值为 $A_i$ 的纪念品。 考虑如下问题：

Takahashi 当前在城市 $S$，想要使用若干次直达航班到达城市 $T$（且 $T$ 不同于 $S$）。
每次他到访一个城市（包括 $S$ 和 $T$），都会在该处购买一件纪念品。
如果存在多条从城市 $S$ 到城市 $T$ 的路线，Takahashi 按如下规则决定路线：

他先尽量最小化从城市 $S$ 到城市 $T$ 的直达航班次数。 随后在满足上述条件的路线中，他尝试最大化所购买纪念品的总价值。

判断他是否能够通过直达航班从城市 $S$ 到达城市 $T$。 如果可以，找出满足上述条件的路线的“直达航班次数”和“纪念品总价值”。

给定 $Q$ 对不同的城市 $(U_i,V_i)$。
对于每个 $1\leq i\leq Q$，当 $S=U_i$ 且 $T=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$ 行 $(1\leq i\leq Q)$ 应当输出 如果无法从城市 $U_i$ 到达城市 $V_i$，则输出 $Impossible$； 如果可以，该行应包含满足上述条件的“直达航班次数”和“纪念品总价值”，按此顺序并以空格分隔。

5
30 50 70 20 60
NYYNN
NNYNN
NNNYY
YNNNN
YNNNN
3
1 3
3 1
4 5

1 100
2 160
3 180

2
100 100
NN
NN
1
1 2

Impossible

提示

$2 \leq N \leq 300$ $1\leq A_i\leq 10^9$ $S_i$ 是一个由 $Y$ 和 $N$ 组成的长度为 $N$ 的字符串。 第 $i$ 个字符串 $S_i$ 的第 $i$ 个字符为 $N$。 $1\leq Q\leq N(N-1)$ $1\leq U_i,V_i\leq N$ $U_i\neq V_i$ 若 $i \neq j$，则 $(U_i,V_i)\neq (U_j,V_J)$。 $N,A_i,Q,U_i$ 和 $V_i$ 都是整数。对于 $(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$。
也可能根本不存在直达航班。

标签: AtCoder|abc286E

来源

AtCoder|abc286E