Score : $500$ points

问题描述

设有 $N$ 座城市，同时存在连接不同城市的单向直达航班。 直达航班的可用性由 $N$ 个长度为 $N$ 的字符串 $S_1,S_2,\ldots,S_N$ 表示。如果 $S_i$ 的第 $j$ 个字符是 Y，表示存在从城市 $i$ 到城市 $j$ 的直达航班；如果是 N，则表示不存在该航班。 每个城市都出售一种纪念品，其中城市 $i$ 出售的价值为 $A_i$ 的纪念品。

考虑以下问题：

高桥当前在城市 $S$，他想通过一些直达航班到达另一个不同的城市 $T$。 每当他访问一个城市（包括 $S$ 和 $T$），他都会在那里购买一个纪念品。 如果从城市 $S$ 到城市 $T$ 存在多条路线时，高桥会按以下方式决定路线：

• 他尽量使从城市 $S$ 到城市 $T$ 的路线中的直达航班数量最小化。
• 然后尽量使购买的纪念品总价值最大化。

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

已给出 $Q$ 对不同的城市 $(U_i,V_i)$。 对于每个 $1\leq i\leq Q$，请计算当 $S=U_i$ 且 $T=V_i$ 时，上述问题的答案。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There are $N$ cities. There are also one-way direct flights that connect different cities.
The availability of direct flights is represented by $N$ strings $S_1,S_2,\ldots,S_N$ of length $N$ each. If the $j$-th character of $S_i$ is Y, there is a direct flight from city $i$ to city $j$; if it is N, there is not.
Each city sells a souvenir; city $i$ sells a souvenir of value $A_i$.

Consider the following problem:

Takahashi is currently at city $S$ and wants to get to city $T$ (that is different from city $S$) using some direct flights.
Every time he visits a city (including $S$ and $T$), he buys a souvenir there.
If there are multiple routes from city $S$ to city $T$, Takahashi decides the route as follows:

• He tries to minimize the number of direct flights in the route from city $S$ to city $T$.
• Then he tries to maximize the total value of the souvenirs he buys.

Determine if he can travel from city $S$ to city $T$ using the direct flights. If he can, find the "number of direct flights" and "total value of souvenirs" in the route that satisfies the conditions above.

You are given $Q$ pairs $(U_i,V_i)$ of distinct cities.
For each $1\leq i\leq Q$, print the answer to the problem above when $S=U_i$ and $T=V_i$.

Constraints

• $2 \leq N \leq 300$
• $1\leq A_i\leq 10^9$
• $S_i$ is a string of length $N$ consisting of Y and N.
• The $i$-th character of $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$, then $(U_i,V_i)\neq (U_j,V_J)$.
• $N,A_i,Q,U_i$, and $V_i$ are all integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines.
The $i$-th $(1\leq i\leq Q)$ line should contain Impossible if he cannot travel from city $U_i$ to city $V_i$; if he can, the line should contain "the number of direct flights" and "the total value of souvenirs" in the route chosen as described above, in this order, separated by a space.

Sample Input 1

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

Sample Output 1

1 100
2 160
3 180

For $(S,T)=(U_1,V_1)=(1,3)$, there is a direct flight from city $1$ to city $3$, so the minimum possible number of direct flights is $1$, which is achieved when he uses that direct flight. In this case, the total value of the souvenirs is $A_1+A_3=30+70=100$.

For $(S,T)=(U_2,V_2)=(3,1)$, the minimum possible number of direct flights is $2$. The following two routes achieve the minimum: cities $3\to 4\to 1$, and cities $3\to 5\to 1$. Since the total value of souvenirs in the two routes are $70+20+30=120$ and $70+60+30=160$, respectively, so he chooses the latter route, and the total value of the souvenirs is $160$.

For $(S,T)=(U_3,V_3)=(4,5)$, the number of direct flights is minimum when he travels cities $4\to 1\to 3\to 5$, where the total value of the souvenirs is $20+30+70+60=180$.

Sample Input 2

2
100 100
NN
NN
1
1 2

Sample Output 2

Impossible

There may be no direct flight at all.

update @ 2024/3/10 11:57:58