ABC271E Subsequence Path 题解

序列dp

题目大意

有 $N$ 个点 $M$ 条边，每一条边都是双向边，第 $i$ 条道路连接着 $A_i$ 和 $B_i$，长度为 $C_i$。现在有一个长度为 $K$ 的序列，第 $i$ 个数为 $E_i$ $(1\le E_i\le M)$。接下来你需要在这个序列当中选择若干个数，使得这些数对应的边连接起一条 $1$ 到 $N$ 的路径，问你这一条路径的最小长度。如果没有，输出 $-1$。

思路

看到在 $K$ 个数当中选择若干个数，我们果断选择 dp。我们设 $d{p}_{(i,j)}$ 表示为选择了前 $i$ 个数对应的边，$1$ 到 $j$ 的最小距离。那么对于第 $i$ 条边，我们可以选择选与不选，因为对后面的决策毫无影响，在其中取最小值就行了：

$$d{p}_{(i,B_{(E_i)})}=\min (d{p}_{(i-1,B_{(E_i)})},d{p}_{(i-1,a_{(A_i)})}+C_{(E_i)})$$

接着，我们发现了 $dp$ 数组内存占用过大，而且每一次转移时，首先就需要将上一层的状态全部拷贝下来，而根本就没有用到本层状态，因此我们可以压数组，把 $i$ 这个维度给压掉，这样子就可以愉快地通过此题了。时间复杂度：$\mathcal{O}(\max (M,K))$，空间复杂度 $\mathcal{O}(N)$。

代码

#include <iostream>
 
using namespace std;
using ll = long long;      // 10^9 累加会爆 int
 
const ll kMaxN = 2e5 + 5;  // 最大边数和点数
 
ll a[kMaxN], b[kMaxN], c[kMaxN], e[kMaxN], dp[kMaxN], n, m, k;
 
int main() {
  cin >> n >> m >> k;
  for (ll i = 1; i <= m; i++) {
    cin >> a[i] >> b[i] >> c[i];
  }
  for (ll i = 1; i <= k; i++) {
    cin >> e[i];
  }
  fill(dp + 2, dp + n + 1, 1e18);                           // 初始化 dp 数组，注意不初始化 dp[1]，dp[1] 仍为 0
  for (ll i = 1; i <= k; i++) {                             // 枚举第 i 个数
    dp[b[e[i]]] = min(dp[b[e[i]]], dp[a[e[i]]] + c[e[i]]);  // 不选和选取最小值
  }
  cout << (dp[n] == 1e18 ? -1 : dp[n]) << '\n';  // 判断是否能够到达并输出
  return 0;
}