Skip to content

12203: 【原2203】在一起

题目

题目描述

author: htx 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/2203

Description

XJ和JSL是一对好朋友,他们希望每天能多碰到几次,多打几个招呼,这样会觉得十分得温馨。
但是,因为各种原因,两人在不同的实验室,每天也会从不同的地方出发去实验室,同时,因为是学信息学的,两人都会选择一条最短路来走。现在他们希望每天碰到的机会最大,即,他们走的路的公共部分最长。
简而言之,就是给出一个无向图,和两对点,求这两对点的最短路的最长公共长度。

Input Format

共M+2行,表示一个无向图
第1行:N和M,表示图中共有N个点和M条边,题目中不会有重边和自环。
第2行:a1,b1,a2,b2,其中a1,b1是第一对点,a2,b2是第二对点。
第3~M+2行,表示每条边的两个点和边权。

Output Format

一行,输出这两对点的最短路的最长公共长度。

Hint

30%的数据:N<=10,M<=20。
100%的数据:N<=2000。

Sample Input

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

Sample Output

3

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!