题目：AT_abc271_e
题意
-
给定 \(n\) 个点 \(m\) 条边的有向带权无环图和长度为 \(k\) 的数组 \(E\)，第 \(i\) 条边的起点，终点和点权分别为 \(A_i, B_i, C_i\)，现在需要找到一条最短从 \(1\) 到 \(n\) 的路径使得经过的边的编号组成的序列为 \(E\) 的子序列，没有路径输出 \(-1\)。
-
数据范围：\(2 \le n \le 2 \times 10^5,1 \le m,k \le 2 \times 10^5, 1 \le C_i \le 10^9\)。
思路
-
这个题看起来是最短路，其实它是披着最短路外表的 \(DP\)
（虽然最短路也能做）， -
先来个暴力状态，令 \(dp_i\) 表示走的最后一条边为 \(i\) 的最小路径长度，那么 \(dp_i = \min\limits_{j = 0}^ n\{dp_j + 1\}(B_j = A_i)\)。显然是平方级复杂度，超时。
-
既然把边做状态不行，就那点做状态，但是拓扑序还是边的编号，和神奇。枚举到第 \(i\) 条边时，\(dp_{B_i} = min(dp_{B_i}, dp_{A_i} = 1)\)。注意 \(dp_1 = 0，dp_{i} = \infty(2 \le i \le n)\)。
-
时间复杂度
- 状态数：\(O(n)\)
- 转移数：\(O(m)\)。
- 总时间复杂度：\(O(n+m)\)