Warshall-Floyd. \(O(N^{3})\) が間に合う．
(最短距離，お土産の最大化) の優先順位で同時に処理する． つまり，辞書順を用いればよく，pair を使えばよい． 最大化の方は，マイナスをつければ最小化に帰着できる．
実装
パスの頂点すべてでお土産を買う． 遷移するときに，辺の始点のお土産を買うことにする． 終点の分は後で追加する．
コストの初期化は，頂点\(i\)から \(i\) へのコストが \( (0,0) \)になる．滞在してお土産を買い続けない様に， お土産は 0 にする．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
vll a(n); rep(i,n) { cin >> a[i]; }
vvll to(n);
rep(i,n){
string s ; cin >> s;
rep(j,n){
if(s[j] == 'Y') {
to[i].push_back(j);
// co[i][j] = {1, -a[j]}; // ** どちらでも AC
co[i][j] = {1, -a[i]}; // **
}
}
}
// rem: not {0, -a[i]}
// {0, -a[i]} にしてしまうと，s -> t の path の途中で，
// i -> i を繰り返していくらでも value を高めることができてしまう．
rep(i,n) co[i][i] = {0, 0};
rep(k, n) rep(cu,n) rep(ne,n){
chmin(co[cu][ne], co[cu][k] + co[k][ne]);
}
ll q; cin >> q;
rep(qi,q){
ll s,t; cin >> s >> t;
--s, --t;
auto [d,v] = co[s][t];
v *= -1;
// v += a[s];
v += a[t];
if(d >= INFL) {
cout << "Impossible" << endl;
}else{
cout << d << " " << v << endl;
}
}
return 0;
}
