P2176 [USACO14FEB]路障Roadblock

    • 474通过
    • 1.4K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 图论 搜索 最短路 USACO 2014
  • 难度 普及+/提高
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    每天早晨,FJ从家中穿过农场走到牛棚。农场由 N 块农田组成,农田通过 M 条双向道路连接,每条路有一定长度。FJ 的房子在 1 号田,牛棚在 N 号田。没有两块田被多条道路连接,以适当的路径顺序总是能在农场任意一对田间行走。当FJ从一块田走到另一块时,总是以总路长最短的道路顺序来走。

    FJ 的牛呢,总是不安好心,决定干扰他每天早晨的计划。它们在 M 条路的某一条上安放一叠稻草堆,使这条路的长度加倍。牛希望选择一条路干扰使得FJ 从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。

    输入输出格式

    输入格式:

    第 1 行:两个整数 N, M。

    第 2 到 M+1 行:第 i+1 行包含三个整数 A_i, B_i, L_i,A_i 和 B_i 表示道路 i 连接的田的编号,L_i 表示路长。

    输出格式:

    第 1 行:一个整数,表示通过使某条路加倍而得到的最大增量。

    输入输出样例

    输入样例#1: 复制
    5 7
    2 1 5
    1 3 1
    3 2 8
    3 5 7
    3 4 3
    2 4 7
    4 5 2
    输出样例#1: 复制
    2

    说明

    【样例说明】

    若使 3 和 4 之间的道路长加倍,最短路将由 1-3-4-5 变为 1-3-5。

    【数据规模和约定】

    对于 30%的数据,N <= 70,M <= 1,500。

    对于 100%的数据,1 <= N <= 100,1 <= M <= 5,000,1 <= L_i <= 1,000,000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。