Problem 3311 --最长路径

3311: 最长路径

上一题 正确率: $100.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $1$ 正确数量 $1$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

设 G 为有 n个顶点的带权有向无环图，G中各顶点的编号为 1 到 n，请设计算法，计算图 G中 <1,n>间的最长路径。

Input

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

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

Output

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

若 1 与 n 不联通，请输出 -1。

Sample Input复制

2 1
1 2 1

Sample Output复制

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

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