Subsequence Path（图论，DP）

题意

给定\(N\)个点，\(M\)条边的无向图，边权为\(C_i\)。

给定一个序列\(E = (E_1, E_2, \dots, E_K)\)，其中\(E_i\)表示边的编号。

路径是“好路径”当且仅当边的编号按照经过顺序排序，为\(E\)的子序列（不要求连续）。

求从\(1\)号点到\(N\)号点的好路径中的最短路。

题目链接：https://atcoder.jp/contests/abc271/tasks/abc271_e

数据范围

\(2 \leq N \leq 2 \times 10^5\)
\(1 \leq M, K \leq 2 \times 10^5\)
\(1 \leq C_i \leq 10^9\)
\(1 \leq E_i \leq M\)

思路

这道题独立做出来了，但是由于这个题目非常经典，因此在这里记录一下做法。

考虑DP，\(f(i)\)表示从\(1\)号点通过好路径到达\(i\)号点的最短路径长度。并将\(f\)初始化为\(+\infty\)

遍历\(E\)序列，表示路径的最后一条边为\(E_i\)，然后更新\(f\)。这样即可得到\(1\)号点到所有点的最短距离了。

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 200010;

int n, m, k;
ll f[N];
int a[N];

struct Edge
{
    int u, v;
    ll w;
}e[N];

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for(int i = 1; i <= m; i ++) {
        int u, v;
        ll w;
        scanf("%d%d%lld", &u, &v, &w);
        e[i] = {u, v, w};
    }
    for(int i = 1; i <= k; i ++) scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++) f[i] = 1e18;
    f[1] = 0;
    for(int i = 1; i <= k; i ++) {
        int id = a[i];
        int u = e[id].u, v = e[id].v;
        ll w = e[id].w;
        f[v] = min(f[v], f[u] + w);
    }
    if(f[n] == 1e18) f[n] = -1;
    printf("%lld\n", f[n]);
    return 0;
}