通る道の長さの最小を求める．最小の長さの合計ではない．
良いpath
良いpath とはどういうものかを考えると， \(E\) を先頭から見ていくことで判定できる． そこで \(E\) を基準に考える．
また，良いpath 自体は多くなりうるので，Dijikstra などで すべての良いpath を列挙するのは無理そうなので， そういう意味でも \(E\) を基準に考える．
Inplace DP (inline DP)
\(dp_{i,j} := \) \(E_{[0,j)}\) まで，last が \(i \in V\) minimam cost of good paths
とする． このままだと，時間計算量が \(O(NK)\)．空間計算量は \(O(NK)\) or \(O(N+K)\).
遷移は少ない．\(j\) を固定すると，使う可能性がある辺は \(s_{j} \xrightarrow{j} t_{j}\) のみ． よって，inplace により時間計算量を \(O(N+K)\) に減らすことができた．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m,k ;
cin >> n >> m >> k;
rep(i,m){
ll a,b,c; cin >> a >> b >> c;
--a, --b;
ed[i] = {c,a,b};
}
vll e(k);
rep(i,k) {
cin >> e[i]; --e[i];
}
// inplace なので，j in K の情報は不要．
// 一つの配列を使いまわすのが inplace.
vll dp(n, INFL);
chmin(dp[0], 0LL);
rep(i,k) {
auto [c,a,b] = ed[e[i]];
chmin(dp[b], c + dp[a]);
}
ll ans = dp[n-1];
if(ans >= INFL) ans = -1;
cout << ans << endl;
return 0;
}
