TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2445
  • 题目
  • P2445【三校共训5】正则表达式
    限制 : 时间限制 : 20000 MS   空间限制 : 165536 KB
    评测说明 : 1s
    问题描述

    小沐同学一日意外的看到小原写了一个正则表达式的高级程序,这个正则表达式程序仅仅由字符“0”,“1”,“.”和“*”构成,但是他能够匹配出所有在OJ 上都AC 的程序的核心代码!小沐颇感好奇,于是他决定入侵小原的电脑上去获得这个正则表达式的高级程序。

    在互联网络中的每台电脑并不是直接一对一连通的,而是某些电脑之间存在单向的网络连接,也就是说存在 A 到 B 的连接不一定存在B 到A 的连接,并且有些连接传输速度很快,有些则很慢,所以不同连接传输所花的时间是有大有小的。

    另外,如果存在A 到B 的连接的同时也存在B 到A 的连接的话,那么A 和B 实际上处于同一局域网内,可以通过本地传输,所以花费的传输时间为0。现在小沐告诉你整个网络的构成情况,他希望知道从他的电脑(编号为 1)到小原的电脑(编号为 n)所需要的最短传输时间。

    输入格式

    第一行两个整数 n, m,表示有n 台电脑,m 个连接关系。
    接下来 m 行,每行三个整数 u,v,w;表示从电脑 u 到电脑v 传输信息的时间为w。

    输出格式

    输出文件仅一行为最短传输时间,保证有解。

    样例输入

    输入样例1:
    3 2
    1 2 1
    2 3 1
    输入样例2:
    5 5
    1 2 1
    2 3 6
    3 4 1
    4 2 1
    3 5 2

    样例输出

    输出样例1:
    2
    输出样例2:
    3

    提示

    【数据范围】
    对于 40%的数据,1<=n<=1000, 1<=m<=10000
    对于 70%的数据,1<=n<=5000, 1<=m<=100000
    对于 100%的数据,1<=n<=200000, 1<=m<=1000000, 1<=w<=10000