题目描述
圣玛格丽特学园的一角有一个巨大, 如迷宫般的花坛. 大约有一个人这么高的大型花坛, 做成迷宫的形状, 深受中世纪贵族的喜爱. 维多利加的小屋就坐落在这迷宫花坛的深处. 某一天早晨, 久城同学要穿过这巨大的迷宫花坛, 去探望感冒的维多利加.
整个迷宫可以用 N 个路口与 M 条连接两个不同路口的无向通道来描述. 路口被标号为 1 到 N, 每条通道有各自的长度. 整个迷宫一定是连通的, 迷宫中可能存在若干个环路, 但是, 出于美观考虑, 每个路口最多只会属于一个简单环路. 例如, 图 1 所示的迷宫是非常美观的, 但图 2 则不符合我们的描述, 因为 3 号路口同属于两个简单环.
你需要回答多个这样的询问: 假如久城处在路口 x, 维多利加的小屋处在路口 y, 久城最短需要走多少距离才能到达小屋?
输入数据
第一行 2 个整数 N,M, 表示迷宫花坛的路口数和通道数;
接下来 M 行, 每行 3 个整数 x,y,z, 描述一条连接路口 x 与路口 y, 长度为 z 的通道;
再接下来 1 行包含一个整数 Q, 表示询问数量;
之后 Q 行, 每行 2 个整数 x,y, 描述一个询问.
输出数据
对于每个询问输出一行一个整数, 表示最短距离.
样例输入
- 4 4
- 1 2 1
- 2 3 2
- 1 3 2
- 3 4 1
- 2
- 2 4
- 1 3
样例输出
3 2
数据范围
对于 30%30% 的数据, N≤100N≤100;
另有 30%30% 的数据, 保证 N=MN=M;
对于 100%100% 的数据, 1≤N≤100000,0≤Q≤200000,1≤x,y≤N,1≤z≤10001≤N≤100000,0≤Q≤200000,1≤x,y≤N,1≤z≤1000.
由于传题人比较懒, hack 数据只需满足是一个仙人掌
题目分析
这是一道神题啊, 我看得一脸懵逼. 首先我们发现这是一道图论题 (废话), 我们用 SPFA 还是 DJ 随意. 题目被简化为: 给出一个有向图, 这个图的每个点最多属于一个正环. 我们需要求的是两个点的图上最短距离. 环里面不可能跑两遍的, 其实这是强连通分量.
来源: http://www.bubuko.com/infodetail-3000988.html