Problem C
Torrent Routing
Languages
en
sv
John is trying to download a file using torrent. Torrent
works by storing data in a network of users that upload and
download bits of data from each other. To download the file
John wants, he needs to connect to several users and download
the bits of data necessary to complete his file. However, John
needs to remain anonymous while doing all of this. To solve
this problem, John has decided to route his internet traffic
through a number of servers to hide his IP-address. The
internet bandwidth between servers and users vary. Some servers
are only connected to some other servers/users.
It’s given that the id of John’s PC always is $0$ and that every server/user has a
unique id, it’s also guaranteed that John can connect to every
desired user through some series of connections. John can only
download one bit of data at a time and the time to download the
required data from a user is the sum of the transfer time
between all connections required to reach that user. Help John
determine the minimum download time for his file by routing his
internet traffic optimally.
Input
The first line of input consists of two non-negative
integers $B$ $(1 \leqslant B \leqslant 3000)$, the
number of different users John needs to connect to, and
$N$ $(1 \leqslant N \leqslant 3000)$, the
number of different servers/users. The following $B$ lines each contain two whitespace
seperated non-negative integers: $U_ i$, $F_ i$, $(1 \leqslant U_ i \leqslant N, 1 \leqslant
F_ i \leqslant 10^9)$, the id for that user and the size
of the file John needs from that user (in bits).
The next line contains a single integer $M$ $(1
\leqslant M \leqslant 30000)$, the number of connections
between servers and users (including John).
Then follows N lines that each contain three whitespace
separated non-negative integers $X_ i$, $Y_ i$, $W_ i$ $(1 \leqslant X_ i, Y_ i \leqslant 3000, 1
\leqslant W_ i \leqslant 10^9)$, signifying a connection
between servers/users with id $X_
i$ and $Y_ i$, with
a file transfer speed of $W_
i$ bits/second.
1 Output
Output a single integer, the minimum amount of seconds (rounded to the smallest integer larger or equal to the answer) it takes for John to download all the required bits of data to complete his file.
2 Scoring
Your solution will be tested on several test case groups. To
get the points for a group, it must pass all the test cases in
the group.
|
Group |
Point value |
Constraints |
|
$1$ |
$20$ |
$B, N \leqslant 8$ |
|
$2$ |
$30$ |
$F_ i, W_ i = 1$ for every $1 \leqslant i \leqslant B$. |
|
$3$ |
$50$ |
No further constraints. |
Explanation for Sample 1
The fastest method is to route through server 2. The path 0-1-2-3 takes $\frac{100}{10} + \frac{100}{10} + \frac{100}{21} = 24.762$ seconds. The answer is therefore $25$ seconds.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 3 3 100 4 0 1 10 1 3 1 1 2 10 2 3 23 |
25 |
