AtCoder が提供しているABC（AtCoder Beginner Contest）271 のE問題をC++とPythonで解いてみました。ABC271は、2022年10月1日21:00に実施されました。
AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。
E問題 Subsequence Path（Difficulty : 1402）
問題はリンク先をご覧ください。
グラフの問題ではなく、良い経路に着目したDPで解きます。AtCoder Problems による Difficulty は、1402 でした。
解答案
問題を読むと、グラフの問題のように見えます。
ただし、頂点1から頂点$N$までのすべての経路を列挙して、その経路が数列$E$の部分列になる場合の辺の長さの最小値は？、という発想では解けません。経路の候補が多すぎるためです。
数列$E$に着目して、数列$E$の部分列の経路を通り、頂点1から頂点$N$までの辺の長さの最小値は？という考えで解いてみます。部分和問題に近いかもしれません。
$DP_{i,j}$ を頂点1から頂点$j$まで行く経路で、数列 $E_i$ までの要素 $(E_1, E_2, \cdots, E_i)$ の部分列となる場合の辺の長さの最小値とします。
まず、すべての $j$ に対して、以下の漸化式で初期化します。
$$DP_{i+1, j} = DP_{i, j}$$
次に $A_{E_{i+1}} \rightarrow B_{E_{i+1}} $ の辺の長さが $C_{E_{i+1}}$ であることを使うと、以下の漸化式で更新できます（左辺との最小値を取る必要がありますが）。
$$DP_{i+1, B_{E_{i+1}}} = DP_{i, A_{E_{i+1}}} + C_{E_{i+1}}$$
初期値は、
$$DP_{i, 1} = 0,\; DP_{i, j}\; (1 \leqq i \leqq M,\; j \neq 1)$$
となります。
C++ プログラム例（ABC271E）
$DP$ は二次元で説明しましたが、次の $i+1$ の $DP$ を更新するために $i$ の値をベースとしているため、in-plase で書き換えることができます（23、26行目）。
以下が、C++プログラムです。
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF (1ULL << 60)
int main()
{
int n, m, k;
cin >> n >> m >> k;
vector<int> a(m), b(m);
vector<ll> c(m);
for (int i = 0; i < m; ++i) {
cin >> a[i] >> b[i] >> c[i];
}
vector<int> e(k);
for (int i = 0; i < k; ++i) {
cin >> e[i];
--e[i];
}
vector<ll> dp(n + 1, INF);
dp[1] = 0;
for (int i = 0; i < k; ++i) {
if (dp[a[e[i]]] < INF) {
dp[b[e[i]]] = min(dp[b[e[i]]], dp[a[e[i]]] + c[e[i]]);
}
}
if (dp[n] >= INF) {
cout << -1 << endl;
} else {
cout << dp[n] << endl;
}
return 0;
}AC（Accepted＝正しいプログラム）と判定されました。
Python プログラム例（ABC271E）
Python 版も基本的な考え方は同じです。以下がそのプログラムです。
"""AtCoder Beginner Contest 271 E"""
INF = 1 << 60
n, m, k = map(int, input().split())
a = [0] * m
b = [0] * m
c = [0] * m
for i in range(m):
a[i], b[i], c[i] = map(int, input().split())
e = list(map(int, input().split()))
for i in range(k):
e[i] -= 1
dp = [INF] * (n + 1)
dp[1] = 0
for i in range(k):
if dp[a[e[i]]] < INF:
dp[b[e[i]]] = min(dp[b[e[i]]], dp[a[e[i]]] + c[e[i]])
print(dp[n] if dp[n] < INF else -1)Python 版も「AC」と判定されました。
最後に
ABC271に参加した時には、DPはまったく解けませんでした。この問題は読むことすらできませんでした。
一見するとグラフの問題に見えます。見た目に惑わされず本質的な問題の構造が読み取れれば、DPとして解くことができたと考えています。
引き続き ABC の問題を紹介していきます。
