Subsequence Path

题意

有 \(n\) 个城市和 \(m\) 条有向道路，编号从 \(1\) 开始，第 \(i\) 条道路从 \(a_i\) 到 \(b_i\)，长度为 \(c_i\)。

给定一个长度为 \(k\) 的序列 \(e\)，我们定义从 \(1\) 到 \(n\) 的一条路径是优秀的当且仅当：

• 经过的边的编号按顺序构成 \(e\) 的一个子序列。

求从 \(1\) 到 \(n\) 的优秀路径长度最小值，如果不存在，输出 -1。

数据范围

• \(2 \leqslant n \leqslant 2 \times 10^5\)，\(1 \leqslant m, k \leqslant 2 \times 10^5\)。
• \(1 \leqslant a_i, b_i \leqslant n,\ a_i \ne b_i\ (1 \leqslant i \leqslant m)\)。
• \(1 \leqslant c_i \leqslant 10^9\ (1 \leqslant i \leqslant m)\)。
• \(1 \leqslant e_i \leqslant m\ (1 \leqslant i \leqslant k)\)。

思路

看起来是一道图论题，但实际上是动态规划！

因为题目要求是 \(e\) 序列的一个子序列，那就可以变成一个类子序列 dp。

• 状态：\(dp_i\) 表示走到城市 \(i\) 的最短距离。
• 转移：对于 \(1 \leqslant i \leqslant k\)，\(dp_{b_{e_i}} = \min({dp_{a_{e_i}} + c_{e_i}, dp_{b_{e_i}}})\)。
• 初始状态：\(dp_1=0\)。
• 目标状态：\(dp_n\)。

不开 long long 见祖宗！

复杂度

• 时间：\(O(n+m+k)\)
• 空间：\(O(n+m)\)

Code

#include <iostream>

using namespace std;
using ll = long long; // 前排提示：不开 long long 见祖宗！

const int N = 2e5 + 10;

int n, m, k, e, a[N], b[N], c[N];
ll dp[N];

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 2; i <= n; i++) {
    dp[i] = 1e18; // 赋值最大值
  }
  for (int i = 1; i <= m; i++) {
    cin >> a[i] >> b[i] >> c[i]; // 记录每条边
  }
  for (int i = 1; i <= k; i++) {
    cin >> e;
    dp[b[e]] = min(dp[b[e]], dp[a[e]] + c[e]); // 转移
  }
  cout << (dp[n] < 1e18 ? dp[n] : -1);
  return 0;
}