4171:Paper Route

题目描述
As a poor, tuition-ridden student, you've decided to take up a part time job as a paperboy/papergirl.
You've just been handed your paper route: a set of addresses (conveniently labelled 1 to N).

Every morning, you start at the newspaper office (which happens to be address number 0). You have to plan a route to deliver a newspaper to every address - and you also want to get to class right after you're done.
Conveniently, there are only N roads in your area connecting the addresses, and each of them takes a known time to traverse.
Also, you've precalculated the time it takes to get to Waterloo campus from each address, including the newspaper office (through some combination of biking, busing, or hitching a ride).
How soon can you be done delivering papers and be in your seat at school?
输入解释
Input consists of a number of cases, for each case:
First, there will be a single integer N (the number of addresses, 1 ≤ N ≤ 100,000).
Next, there will be N+1 lines, each with an integer ci (starting with i = 0, 0 ≤ ci ≤ 1,000,000,000), the time it takes to get from location i to campus.
Finally, the input will contain N lines, each with three integers a, b, c (0 ≤ a, b ≤ N, a != b, 0 ≤ c ≤ 1,000). Each of these lines describes a road between locations a and b taking c minutes to traverse.
It is guaranteed that you will be able to reach all the addresses. (Remember that location 0 is the newspaper office.)
输出解释
Output the minimum time it will take to deliver all the papers and get to class.
输入样例
2
1
3
4
0 1 1
0 2 2
输出样例
7
来自杭电HDUOJ的附加信息
Recommend lcy

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-4171

最后修改于 2020-10-25 23:10:55 UTC 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000/1000MS(Java/Others) 32768/32768K(Java/Others)

·

·

·

·

登陆或注册以提交代码