まず、お土産の事を考えずに、都市 \(S\) から都市 \(T\) に移動する事が可能か判定し、移動できる場合は使用する直行便の本数の最小値を求める事を考えます。これは都市を頂点、直行便を重さ \(1\) の有向辺としたグラフにおいて最短経路問題を解くことによって求める事ができます。これを改良して、最短経路の中での購入するお土産の価値の総和の最大値を求められるようにしたいです。

現状ではお土産の価値は頂点と紐づけられており、直接、最短経路問題として解くことはできません。 しかし、ここで、最短経路の性質について考えると、同じ都市を \(2\) 回以上訪れることはありません。そのため、都市 \(S\) から都市 \(T\) へ移動する高橋君の行動を次のように書き換える事ができます。

• 高橋君はまず出発都市で 価値 \(A_S\) のお土産を購入する。
• その後、「都市 \(U_i\) から 都市 \(V_i\) へ移動し、価値 \(A_{V_i}\) のお土産を購入する」という行動を繰り返し、都市 \(T\) へ移動する。

\(S,T\) を固定した時、任意の経路において\(1\) つめのステップは共通なので、\(2\) つめのステップにおける(最短距離, 最短経路の中での価値の総和の最大値)を求めれば良いです。 \(\cdots (*)\)

これは、普通の最短経路問題において \(d(X,Y)\) で都市 \(X\) から都市 \(Y\) への(暫定的な)最短距離を表し更新する部分を、\((d(X,Y), val(X,Y))\)で(都市 \(X\) から都市 \(Y\) への(暫定的な)最短距離, (暫定的な)最短距離を達成する経路の中でのお土産の価値の総和の(暫定的な)最大値)を更新するように書き換えれば良いと分かります。

この時、辺 \(i\) による更新は、

• \(d(X,U_i)+1<d(X,V_i)\)

または

• \(d(X,U_i)+1=d(X,V_i)\) かつ \(val(X,U_i)+A_{V_i}>val(X,V_i)\)

の時に \((d(X,V_i),val(X,V_i))\leftarrow (d(X,U_i)+1,val(X,U_i)+A_{V_i})\) と更新すれば良いです。( \(val(X,Y)\) の符号を反転させれば、辞書順で小さいものに書き換えるということもできます。)

よって、このような更新を用いて、ワーシャルフロイド法を用いて任意の \(2\) 点対間について答えを求める事ができます。計算量は \(O(N^3)\) であり、十分高速です。
なお、先頭の基準となる \(d(X,Y)\) の値が辺を通ることによって必ず増加するため、いわゆる負閉路は存在しません。 よって、始点を固定した ダイクストラ法等のアルゴリズム でも \(O(N(M+N\log N))\), \(O(NM\log N)\) 等の現実的な時間計算量で解く事ができます。

よって、この問題を解く事ができました。

c++による実装例 :

#include <bits/stdc++.h>
using namespace std;

int main(void) {
	int n;
	long long a[300];
	string s;
	int d[300][300];
    long long val[300][300];

	cin >>n;
	for(int i=0;i<n;i++)cin>>a[i];

	for(int i=0;i<n;i++)for(int j=0;j<n;j++)d[i][j]=n,val[i][j]=0;
	for(int i=0;i<n;i++)d[i][i]=0,val[i][i]=0;
	for(int i=0;i<n;i++){
		cin >> s;
		for(int j=0;j<n;j++){
			if(s[j]=='Y')d[i][j]=1,val[i][j]=a[j];
		}
	}

	for(int j=0;j<n;j++){
		for(int i=0;i<n;i++){
			for(int k=0;k<n;k++){
				if((d[i][j]+d[j][k])<d[i][k]){
					d[i][k]=d[i][j]+d[j][k];
					val[i][k]=val[i][j]+val[j][k];
				}
				else if(((d[i][j]+d[j][k])==d[i][k])&&((val[i][j]+val[j][k])>val[i][k])){
					val[i][k]=val[i][j]+val[j][k];
				}
			}
		}
	}

	int q,u,v;
	cin >> q;
	for(int i=0;i<q;i++){
		cin >> u >> v;
		if(d[u-1][v-1]==n)cout<<"Impossible\n";
		else cout<<d[u-1][v-1]<<" "<<(val[u-1][v-1]+a[u-1])<<"\n";
	}
	return 0;
}