Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
 Register new ID

Watering Hole

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 943    Accepted Submission(s): 212

Problem Description
Farmer John has decided to bring water to his N (2 <= N <= 5,000) pastures which are conveniently numbered 1..N. And He has M (1 <= M <= 25,000) pipes. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000). Connecting pastures i and j with a pipe costs p (1 <= p <= 100,000). Since the length and quality are different, there may be more than one pipes in different costs connecting pasture i and j.

Luckily, farmer John found there was only one plan to minimize his cost.

Farmer Jack, farmer John's friend, has P (1 <= P <= 1,000) pipes. He promised that he could give one pipe to Farmer John, and farmer John can use it to connect his pasture i and j. Now, farmer John wants to know how much the minimum amount he will have to pay to water all of his pastures if he chooses one more pipe from Jack.

There are serveral cases:
Line 1: Three integers: N, M and P

Lines 2: N space-separated integers; the i-th integer is W_i

Lines 3..M+3: Three integers: i, j, p. Means a pipe connecting pasture i and j costs p

Lines M+4..P+M+4: Two Integers: i, j. Farmer Jack can give Farmer John a pipe connecting pasture i and j.

Line 1..P: A single integer denoting the minimum cost of providing all the pastures with water if farmer John chooses the i-th pipe from farmer Jack.

Sample Input
4 6 1 5 4 4 3 1 2 2 1 3 2 1 4 2 2 3 3 2 4 3 3 4 4 3 4

Sample Output


Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-05-31 07:03:14, Gzip enabled