#序列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。我们设 $dp_{(i,j)}$ 表示为选择了前 $i$ 个数对应的边，$1$ 到 $j$ 的最小距离。那么对于第 $i$ 条边，我们可以选择选与不选，因为对后面的决策毫无影响，在其中取最小值就行了：
$
dp_{(i,B_{(E_i)})}=\min(dp_{(i-1,B_{(E_i)})},dp_{(i-1,a_{(A_i)})}+C_{(E_{i})})
$
接着，我们发现了 $dp$ 数组内存占用过大，而且每一次转移时，首先就需要将上一层的状态全部拷贝下来，而根本就没有用到本层状态，因此我们可以压数组，把 $i$ 这个维度给压掉，这样子就可以愉快地通过此题了。时间复杂度：$\mathcal O(\max(M,K))$，空间复杂度 $\mathcal O(N)$。
## 代码
```cpp
#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;
}
```