USACO 2019 January Contest Gold Problem 3 Shortcut
Every evening, Farmer John rings a giant bell that summons his cows to the barn for dinner. Eager to get to the barn as quickly as possible, they all follow the shortest possible route to get there.
The farm is described by a set of NN fields (1≤N≤10,0001≤N≤10,000), conveniently numbered 1…N1…N, with the barn residing in field 1. The fields are connected by a set of MM bidirectional trails (N−1≤M≤50,000N−1≤M≤50,000). Each trail has a travel time associated with it, and there is a path from every field to the barn using some set of trails.
Field ii contains cici cows. Upon hearing the dinner bell, these cows all walk to the barn along a route that takes the minimum amount of time. If there are several routes tied for the minimum time, the cows take whichever of these is "lexicographically" smallest (i.e., they break ties between two routes by favoring the one using the lower-indexed field at the first place where the routes differ, so for example a path that visits fields 7, 3, 6, 1 would be preferable to one that visits 7, 5, 1, assuming both had the same travel time).
Farmer John is worried about the barn being far away from some fields. He adds up the travel time experienced by each cow, summed over all the cows, calling this number the total travel time. He would like to reduce this number as much as possible by adding one extra "shortcut" trail which has a travel time of TT (1≤T≤10,0001≤T≤10,000), from the barn (field 1) to some other field of his choosing. If a cow stumbles upon the shortcut trail while traveling along her usual path to the barn, she will take it if it gets her to the barn faster. Otherwise, a cow will follow her usual route, even if it might have been possible to use the shortcut to improve her travel time.
Please help Farmer John determine the greatest possible amount of decrease in total travel time he can achieve by adding his shortcut trail.
INPUT FORMAT (file shortcut.in):
The first line of input contains NN, MM, and TT. The next line contains NN integers c1…cNc1…cN, each in the range 0…10,0000…10,000. The next MM lines each describe a trail using three integers aa, bb, and tt, where the trail connects fields aa and bb and has travel time tt. All travel times are in the range 1…25,0001…25,000.
OUTPUT FORMAT (file shortcut.out):
Please output the largest possible reduction in total travel time Farmer John can achieve.
SAMPLE INPUT:
5 6 2 1 2 3 4 5 1 2 5 1 3 3 2 4 3 3 4 5 4 5 2 3 5 7
SAMPLE OUTPUT:
40
Problem credits: Brian Dean
国际竞赛真题资料-点击免费领取！
美高学分项目重磅来袭！立即了解
2025欧几里得数学竞赛报名开启！
