Problem 3311 --最长路径

3311: 最长路径

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签
设 G 为有 n个顶点的带权有向无环图,G中各顶点的编号为 1 到 n,请设计算法,计算图 G中 <1,n>间的最长路径。

输入的第一行有两个整数,分别代表图的点数 n和边数 m

第 2 到第 (m + 1) 行,每行 3 个整数 u, v, w,代表存在一条从 u到 v边权为 w 的边。

输出一行一个整数,代表 11 到 nn 的最长路。

若 1 与 n 不联通,请输出 -1

2 1
1 2 1
1
dijkstra不适用负边权的情况,可以考虑bellman或者spfa算法

推荐代码 查看3311 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$5 $ms] 梦尘 728326 2021-04-01 17:12:40
内存最少[$1876 $KB] 梦尘 728326 2021-04-01 17:12:40
第一AC 梦尘 728326 2021-04-01 17:12:40
第一挑战 梦尘 728326 2021-04-01 17:12:40

赛题来源/所属竞赛 最短路径算法 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛