最长路

题目内容

题目描述

设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且如果G中的一条边是从i指向j,则有i < j。设w(i,j)为边的长度,请设计算法,计算图G中从顶点1到顶点n的最长路径。

输入描述

第一行有两个整数n和m(n <= 1500, m <= 50000),表示有n个顶点和m条边,接下来m行中每行输入3个整数a,b,v(表示从a点到b点有条边,边的长度为v,v <= 10^9)。

输出描述

一个整数,即1到n之间的最长路径.如果1到n之间没连通,输出-1。

样例输入

2 1 1 2 1

样例输出

1

提示

提交评测
请登录后再操作

题目描述

最长路
1583
0
08Level8
41
22
54%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在