P2169 正则表达式

    • 674通过
    • 1.3K提交
  • 题目提供者 sdyhdt
  • 评测方式 云端评测
  • 标签 图论 强连通分量,缩点 最短路
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

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

    题目描述

    在Internet网络中的每台电脑并不是直接一对一连通的,而是某些电脑之间存在单向的网络连接,也就是说存在A到B的连接不一定存在B到A的连接,并且有些连接传输速度很快,有些则很慢,所以不同连接传输所花的时间是有大有小的。另外,如果存在A到B的连接的同时也存在B到A的连接的话,那么A和B实际上处于同一局域网内,可以通过本地传输,这样花费的传输时间为0。

    现在小Z告诉你整个网络的构成情况,他希望知道从他的电脑(编号为1),到小X的电脑(编号为n)所需要的最短传输时间。

    输入输出格式

    输入格式:

    第一行两个整数n, m, 表示有n台电脑,m个连接关系。

    接下来m行,每行三个整数u,v,w;表示从电脑u到电脑v传输信息的时间为w。

    输出格式:

    输出文件仅一行为最短传输时间。

    输入输出样例

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

    说明

    对于40%的数据,1<=n<=1000, 1<=m<=10000

    对于70%的数据,1<=n<=5000, 1<=m<=100000

    对于100%的数据,1<=n<=200000, 1<=m<=1000000

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