3606: 送礼物-训练套题T4T3

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

【问题描述】

Farmer John有B头奶牛(1≤B≤25,000)，有N(2*B≤N≤50,000)个农场，编号1．．N，有M(N-1≤M≤100,000)条双向边，第i条边连接农场R_i和S_i (1≤R_i≤N；1≤S_i≤N)，该边长度是Li(1≤Li≤2,000)。

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

【输入数据】

第1行：三个整数：N，M，B。

    第2~M+I行：每行三个整数：R_i，S_i，和 L_i，描述一条边的信息。

    第M+2~M+B+1行：共B行，每行两个整数P_i和Q_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