问题 5321. -- 送礼物-训练套题T4T3

5321: 送礼物-训练套题T4T3

时间限制: 1 Sec  内存限制: 128 MB
献花: 13  解决: 4
[献花][花圈]

题目描述

3. [送礼物cgiving.pas/ c/cpp]

【问题描述】

Farmer JohnB头奶牛(1B25,000),有N(2*BN50,000)个农场,编号1..N,有M(N-1M100,000)条双向边,第i条边连接农场R_iS_i (1R_iN1S_iN),该边长度是Li(1Li2,000)

    居住在农场P_i的奶牛A(1P_iN),它想送一份新年礼物给居住在农场Q_i(1Q_iN)的奶牛B,但是奶牛A必须先到FJ(居住在编号1的农场)那里取礼物,然后再送给奶牛B。你的任务是:奶牛A至少需要走多远的路程?

【输入数据】

1行:三个整数:NMB

    2~M+I行:每行三个整数:R_iS_i,和 L_i,描述一条边的信息。

    M+2~M+B+1行:共B行,每行两个整数P_iQ_i,表示住在P_i农场的奶牛送礼给住在Q_i农场的奶牛。

【输出数据】

B行,每行一个整数,表示住在P_i农场的奶牛送礼物给住在Q_i农场的奶牛至少需要走的路程。

【输入样例】

6  7  3

  1  2  3

  5  4  3

  3  1  1

  6  1  9

  3  4  2

  1  4  4

  3  2  2

  2  4

  5  1

  3  6

【输出样例】

6

6

10

输入

输出

提示


算法分析:



  题目是求任意两个农场AB之间的最短路径,但是中间必须经过农场1。因此我们



求出农场1到其他所有农场的最短路径,然后要求的就是d i s[A]+d i
s[B]
了。由于农场数



量达到,因此直接用朴素的d
i j k s t r a
算法会超时,我们可以优化它,用堆或者胜者树之类的数据结构去实现。时间复杂度:O(ElogN)

来源

[献花][花圈]