ABC271-E 解説

E - Subsequence Path

DPできます。

長さ$N$のDP配列(これは頂点 $1$ からの最短距離を表します)を $dp[1]=0,dp[i]=inf(i > 1)$ で初期化します。そして、各 $E_i$ に対して、$chmin(dp[A_{E_i}], dp[B_{E_i}] + C_{E_i})$ と遷移していきます。これにより、最短経路が更新されていきます。

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())
    A[i] -= 1
    B[i] -= 1
dp = [inf] * N
dp[0] = 0
for E in list(map(int, input().split())):
    E -= 1
    dp[B[E]] = min(dp[B[E]], dp[A[E]] + C[E])
print(dp[N - 1] if dp[N - 1] < inf else -1)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1LL<<60;

int main() {
    int N, M, K, E;
    cin >> N >> M >> K;
    vector<int> A(M), B(M), C(M);
    for (int i = 0; i < M; i++) {
        cin >> A[i] >> B[i] >> C[i];
        A[i]--; B[i]--;
    }
    vector<ll> dp(N, inf);
    dp[0] = 0;
    while (K--) {
        cin >> E; E--;
        dp[B[E]] = min(dp[B[E]], dp[A[E]] + C[E]);
    }
    ll ans = dp[N - 1];
    cout << (ans < inf ? ans : -1) << '\n';
}