/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
N 個の都市があり、いくつかの相異なる都市の間は一方通行の直行便によって移動することができます。
どの直行便が存在するかは N 個の長さ N の文字列 S_1,S_2,\ldots,S_N によって表され、
S_i の j 文字目が Y のとき都市 i から都市 j へ向かう直行便が存在することを、
N のとき存在しないことを示します。
また、各都市ではお土産が 1 つずつ売られており、都市 i では価値 A_i のお土産が売られています。
次のような問題を考えます。
高橋君は今都市 S におり、いくつかの直行便を乗り継いで(S とは異なる)都市 T に向かおうとしています。
さらに、高橋君は移動する途中で訪れた都市(S,T を含む)において 1 つずつお土産を購入します。
都市 S から都市 T へ向かう経路が複数存在する時、高橋君は次のような経路で移動することを考えています。
- 都市 S から 都市 T に向かう経路のうち、使う直行便の数が最小である。
- さらにそのような経路のうち、購入するお土産の価値の総和が最大である。
高橋君が都市 S から T に直行便を乗り継いで移動することが可能か判定し、 可能な時は高橋君が上の条件をみたすように経路を選んだ時の「使用する直行便の本数」と「お土産の価値の総和」を求めよ。
相異なる都市の組 (U_i,V_i) が Q 個与えられます。
各 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 は
YとNのみからなる長さ N の文字列 - 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 は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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 を、
可能な時は上記のように経路を選んだ時の「使用する直行便の本数」と「お土産の価値の総和」をこの順に空白区切りで出力せよ。
入力例 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 の 2 通りが考えられます。 それぞれの経路の時のお土産の価値の総和は 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
直行便が全く存在しないこともあります。
Score : 500 points
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
YandN. - 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.