P5160: 送礼物-训练套题T4T3
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
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
【提示】
算法分析：
题目是求任意两个农场A和B之间的最短路径，但是中间必须经过农场1。因此我们
求出农场1到其他所有农场的最短路径，然后要求的就是d i s[A]+d i
s[B]了。由于农场数
量达到，因此直接用朴素的d
i j k s t r a算法会超时，我们可以优化它，用堆或者胜者树之类的数据结构去实现。时间复杂度：O(ElogN)。