AtCoder が提供しているABC（AtCoder Beginner Contest）286 のE問題をC++とPythonで解いてみました。ABC286は、2023年1月21日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Souvenir（Difficulty : 1128）
問題はリンク先をご覧ください。
Warshell Floyd 法を使って解くことができます。AtCoder Problems による Difficulty は 1128 でした。
解答案
前日に解説した Warshall-Floyd（ワーシャル–フロイド）法を使う応用問題です。
もし、各都市のお土産を考えなければ、距離1の辺を持つグラフに対する全点対間最短経路を Warshall-Floyd 法で求めて終わりです。この最短経路は同じ都市を2回通ることはありません。
この最短経路で、お土産を各都市で購入します。このお土産を価値の最大値は、最短経路が一通りの場合は最短経路と同じように更新できます。つまり、以下の式で更新できます。ここで、dist[i][j] は、都市iと都市jの移動で乗る直行便の最小値、value[i][j] は、都市iと都市jの移動で買うお土産の価値の最大値とします。ただし、valueは始発都市のお土産の価値を含まないとします。
dist[i][k] + dist[k][j] < dist[i][j] なら、以下の式で更新します。
- dist[i][j] = dist[i][k] + dist[k][j]
- value[i][j] = value[i][k] + value[k][j]
最短経路が２つ以上ある場合、お土産の価値は以下の式で更新します。
dist[i][k] + dist[k][j] == dist[i][j] かつ value[i][k] + value[k][j] > value[i][j] ならば
- value[i][j] = value[i][k] + value[k][j]
C++ プログラム例（ABC286E）
上の考察をプログラムとして表現します。$2 \leqq N \leqq 300$ です。最悪計算量は、$O(N^3) = 2.7 \times 10^7$ となり間に合います。
お土産の最大値を出力するときに始発都市のお土産を加えておきます（59行目）。
以下が、C++ のプログラムです。更新のポイントとなるコードの背景色を変更しました。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1 << 30)
int main()
{
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
vector<string> s(n);
for (int i = 0; i < n; ++i) {
cin >> s[i];
}
vector<vector<int>> dist(n, vector<int>(n, INF));
vector<vector<ll>> value(n, vector<ll>(n, 0));
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (s[i][j] == 'Y') {
dist[i][j] = 1;
value[i][j] = a[j];
}
}
}
for (int i = 0; i < n; ++i) {
dist[i][i] = 0;
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if ((dist[i][k] < INF)&&(dist[k][j] < INF)) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
value[i][j] = value[i][k] + value[k][j];
} else if ((dist[i][k] + dist[k][j] == dist[i][j])
&&(value[i][k] + value[k][j] > value[i][j])) {
value[i][j] = value[i][k] + value[k][j];
}
}
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
--u;
--v;
if (dist[u][v] == INF) {
cout << "Impossible" << endl;
} else {
cout << dist[u][v] << " " << a[u] + value[u][v] << endl;
}
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC286E）
Python 版も基本的な考え方は同じです。以下となります。
"""AtCoder Beginner Contest 286 E"""
INF = 1 << 30
n = int(input())
a = list(map(int, input().split()))
s = [input() for i in range(n)]
dist = [[INF for _ in range(n)] for _ in range(n)]
value = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n):
if s[i][j] == 'Y':
dist[i][j] = 1
value[i][j] = a[j]
for i in range(n):
dist[i][i] = 0
for k in range(n):
for i in range(n):
for j in range(n):
if dist[i][k] < INF and dist[k][j] < INF:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
value[i][j] = value[i][k] + value[k][j]
elif dist[i][k] + dist[k][j] == dist[i][j] and \
value[i][k] + value[k][j] > value[i][j]:
value[i][j] = value[i][k] + value[k][j]
q = int(input())
for i in range(q):
u, v = map(int, input().split())
u -= 1
v -= 1
if dist[u][v] == INF:
print("Impossible")
else:
print(dist[u][v], a[u] + value[u][v])このプログラムは、Python (CPython 3.11.4) では、TLE（Time Limit Exceeded）判定でした。一方、Python (PyPy 3.10-v7.3.12) では、AC 判定となりました。
最後に
最短経路（乗る直行便の最小値）とお土産の最大値を処理する必要があります。Warshall-Floyd 法を本質的に理解できていれば解ける問題だと感じました。
引き続き ABC に挑戦して、解説記事を書いていきます。
