6402 Freda的传呼机 0x60「图论」例题
描述
为了随时与rainbow 快速交流,Freda 制造了两部传呼机。Freda 和rainbow 所在的地方有N 座房屋、M 条双向光缆。每条光缆连接两座房屋,传呼机发出的信号只能沿着光缆传递,并且传呼机的信号从光缆的其中一端传递到另一端需要花费t 单位时间。现在Freda 要进行Q 次试验,每次选取两座房屋,并想知道传呼机的信号在这两座房屋之间传递至少需要多长时间。Freda 和rainbow 简直弱爆了有木有T_T,请你帮帮他们吧……
N 座房屋通过光缆一定是连通的,并且这M 条光缆有以下三类连接情况:
A:光缆不形成环,也就是光缆仅有N-1 条。
B:光缆只形成一个环,也就是光缆仅有N 条。
C:每条光缆仅在一个环中。
输入格式
第一行包含三个用空格隔开的整数,N、M 和Q。
接下来M 行每行三个整数x、y、t,表示房屋x 和y 之间有一条传递时间为t 的光缆。
最后Q 行每行两个整数x、y,表示Freda 想知道在x 和y 之间传呼最少需要多长时间。
输出格式
输出Q 行,每行一个整数,表示Freda 每次试验的结果。
样例输入1
5 4 2 1 2 1 1 3 1 2 4 1 2 5 1 3 5 2 1
样例输出1
3 1
样例输入2
5 5 2 1 2 1 2 1 1 1 3 1 2 4 1 2 5 1 3 5 2 1
样例输出2
3 1
样例输入3
9 10 2 1 2 1 1 4 1 3 4 1 2 3 1 3 7 1 7 8 2 7 9 2 1 5 3 1 6 4 5 6 1 1 9 5 7
样例输出3
5 6
数据范围与约定
- 颂芬数据占10%,2<=N<=1000,N-1<=M<=1200。
A 类数据占30%,M=N-1。
B 类数据占50%,M=N。
C 类数据占10%,M>N。
对于100%的数据,2<=N<=10000,N-1<=M<=12000,Q=10000,1<=x,y<=N,1<=t<32768。
来源
石家庄二中【Nescafé 26】杯NOIP模拟赛