P2149 [SDOI2009]Elaxia的路线

    • 632通过
    • 1.8K提交
  • 题目提供者 xmyzwls 管理员
  • 评测方式 云端评测
  • 标签 SPFA 拓扑排序 最短路 各省省选 2009 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    最近,Elaxia和w**的关系特别好,他们很想整天在一起,但是大学的学习太紧张了,他们 必须合理地安排两个人在一起的时间。

    Elaxia和w**每天都要奔波于宿舍和实验室之间,他们 希望在节约时间的前提下,一起走的时间尽可能的长。

    现在已知的是Elaxia和w**所在的宿舍和实验室的编号以及学校的地图:地图上有N个路 口,M条路,经过每条路都需要一定的时间。 具体地说,就是要求无向图中,两对点间最短路的最长公共路径。

    输入输出格式

    输入格式:

    第一行:两个整数N和M(含义如题目描述)。

    第二行:四个整数x1、y1、x2、y2(1 ≤ x1 ≤ N,1 ≤ y1 ≤ N,1 ≤ x2 ≤ N,1 ≤ y2 ≤ N),分别表示Elaxia的宿舍和实验室及w**的宿舍和实验室的标号(两对点分别 x1,y1和x2,y2)。

    接下来M行:每行三个整数,u、v、l(1 ≤ u ≤ N,1 ≤ v ≤ N,1 ≤ l ≤ 10000),表 u和v之间有一条路,经过这条路所需要的时间为l。

    输出格式:

    一行,一个整数,表示每天两人在一起的时间(即最长公共路径的长度)

    输入输出样例

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

    说明

    对于30%的数据,N ≤ 100;

    对于60%的数据,N ≤ 1000;

    对于100%的数据,N ≤ 1500,输入数据保证没有重边和自环。

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