P2349 金字塔

    • 105通过
    • 227提交
  • 题目提供者 NIatraucthoi
  • 评测方式 云端评测
  • 标签 图论 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    有一盗墓者潜入一金字塔盗宝。当她(难道是Lara Croft ?)打开一个宝箱的时候,突然冒出一阵烟(潘多拉的盒子?),她迅速意识到形势不妙,三十六计走为上计……由于她盗得了金字塔的地图,所以她希望能找出最佳逃跑路线。地图上标有N个室,她现在就在1室,金字塔的出口在N室。她知道一个秘密:那阵烟会让她在直接连接某两个室之间的通道内的行走速度减半。她希望找出一条逃跑路线,使得在最坏的情况下所用的时间最少。

    输入输出格式

    输入格式:

    输入文件的第一行有两个正整数N(3≤N≤100)和M(3≤M≤2000);下面有M行,每行有三个数正整数U、V、W,表示直接从U室跑到V室(V室跑到U室)需要W(3≤W≤255)秒。

    输出格式:

    输出所求的最少时间(单位为秒)。

    输入输出样例

    输入样例#1: 复制
    7 8
    1 2 10
    2 3 12
    3 4 20
    4 7 8
    1 7 34
    2 5 10
    5 6 12
    6 4 13
    输出样例#1: 复制
    66

    说明

    样例解释 Sample Explan:

    基本上有三种路线:

    (1)1 -> 2 -> 3 -> 4 -> 7

    总时间为:10+12+20+8=50,最坏的情况是“3->4”那一段,要多花20秒(因为行走速度减半),所以这条路选最坏需要70秒;

    (2)1 -> 2 -> 5 -> 6 -> 4 -> 7

    总时间为:10+10+12+13+8=53,最坏的情况是“6->4”那一段,要多花13秒,所以这条路选最坏需要66秒;

    (3)1 -> 7

    总时间为:34=34,最坏的情况是“1->7”那一段,要多花34秒,所以这条路选最坏需要68秒。

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