Courses

動態規劃

动态图编程

Module: 动态图编程

Problem

5 /7

DAG 的快捷方式

Theory Click to read/hide

在使用动态规划的解决方案中，动态计算的顺序很重要（必须先计算当前值所依赖的值）。
因此，如果需要在有向无环图上使用动态规划，就需要先构造一个图的拓扑排序。然后通过按照构建的拓扑排序的顺序对顶点进行排序来计算动态（根据问题，遍历顺序可以是从源到汇，也可以是从源到汇）。

Problem

给出了一个有向加权无环图。要求在其中求最短路径
从顶点 s 到顶点 t。

输入：
输入文件的第一行包含四个整数 n、m、s 和 t - 图的顶点数、边数、初始顶点数和最终顶点数，分别为 (1 <= n <= 100000; 0 <= m <= 200000; 1 <= s, t <= n).
接下来的 m 行包含边的描述，每行一个。
边编号 i 由三个整数 b_i、e_i 和 w_i 描述 - 分别是边的起点、终点和长度（ 1 <= b _i, e_i <= n;|w_i| <= 1000).
该图不包含循环和循环。

输出：
输出文件的第一行必须包含一个整数——从 s 到 t 的最短路径的长度。
如果没有从 s 到 t 的路径，则打印“Unreachable”。

示例：
<正文>

time 1500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking