最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 最长路

    正文概述 陈老师   2026-01-20 15:31:46  

    题目描述

    设 GG 为有 nn 个顶点的带权有向无环图,GG 中各顶点的编号为 11 到 nn,请设计算法,计算图 GG 中 1,n1, n 间的最长路径。

    输入格式

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

    第 22 到第 (m+1)(m + 1) 行,每行 33 个整数 u,v,wu, v, w(u<vu<v),代表存在一条从 uu 到 vv 边权为 ww 的边。

    输出格式

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

    若 11 与 nn 不连通,请输出 −1-1。

    2 1
    1 2 1
    
    1
    

    数据规模

    • 对于 20%20\%的数据,n≤100n \leq 100,m≤103m \leq 10^3。
    • 对于 40%40\% 的数据,n≤103n \leq 10^3,m≤104m \leq 10^{4}。
    • 对于 100%100\% 的数据,1≤n≤15001 \leq n \leq 1500,0≤m≤5×1040 \leq m \leq 5 \times 10^4,1≤u,v≤n1 \leq u, v \leq n,−105≤w≤105-10^5 \leq w \leq 10^5。
    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 最长路