Nescafe 26 Freda 的传呼机
(communicate.pas/c/cpp) 题目描述 为了随时与 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 Nescafe 26 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。