MinMaxMax | Topcoder Archive

Problem Statement

You are given an undirected graph with n nodes and m edges. The nodes are labeled from 0 to n-1. This graph is guaranteed to be connected and have no self-loops or multiple edges.

You are given a description of the graph: the int[]s a, b, w, and v. For each valid i, there is an edge that connects nodes a[i] and b[i] and has weight w[i]. For each valid j, node j has weight v[j]. All weights are positive integers.

A path in this graph is a sequence of pairwise distinct nodes such that each pair of consecutive nodes is connected by an edge. The difficulty of a path is the value (N times E), where N is the maximum weight of a node on the path (including the nodes where it starts and ends) and E is the maximum weight of an edge on the path.

For each pair of distinct nodes i and j, let d(i,j) be the smallest possible difficulty of a path that connects i and j. Find and return the sum of d(i,j) with 0 ≤ i < j ≤ n-1.

Definition

Class:: MinMaxMax
Method:: findMin
Parameters:: int[], int[], int[], int[]
Returns:: long
Method signature:: long findMin(int[] a, int[] b, int[] w, int[] v)
(be sure your method is public)

Notes

The values of n and m are not explicitly given. n can be inferred from the length of v and m can be inferred from the length of w.

Constraints

n will be between 2 and 300, inclusive.
m will be between n-1 and min(2,500, n choose 2), inclusive.
a,b,w will contain exactly m elements.
It is guaranteed that the graph described by a,b is connected and has no self loops or multiple edges.
Each element of w will be between 1 and 10^6, inclusive.
v will contain exactly n elements.
Each element of v will be between 1 and 10^6, inclusive.

Examples

```
{0}
```
```
{1}
```
```
{5}
```
```
{3,6}
```
```
Returns: 30
```
There are two nodes and a single edge in this graph. Node 0 has weight 3 and node 1 has weight 6. There is an edge between node 0 and node 1 with weight 5. In this case we just want to find d(0,1). This is equal to 5*6=30.
```
{0,0,1}
```
```
{1,2,2}
```
```
{10,11,12}
```
```
{6,5,4}
```
```
Returns: 186
```
We have the following values: d(0,1)=60 d(0,2)=66 d(1,2)=60
```
{0,0,1}
```
```
{1,2,2}
```
```
{100,1,1}
```
```
{1,1,100}
```
```
Returns: 300
```
In this case each d(i,j) is 100. For example, consider d(0,1). There are two possible paths. The path 0-1 has maximum node weight 1 and maximum edge weight 100, hence its difficulty is 1*100 = 100. The path 0-2-1 has maximum node weight 100 and maximum edge weight 1, hence its difficulty is 100*1 = 100 as well.

{0,1,2,3,4,5,6,7,8,9}

{1,2,3,4,5,6,7,8,9,10}

{1000000,1,1000000,1,1000000,1,1000000,1,1000000,1}

{1000000,1,1000000,1,1000000,1,1000000,1,1000000,1,1000000}

Returns: 50000005000000

Watch out for overflow

{9,12,4,11,0,8,6,11,11,10,12,7,3,12,3,10,0,3,2,7,
0,10,8,1,11,9,2,0,3,6,4,2,3,5,9,0,6}

{0,5,6,5,10,2,1,2,3,4,6,9,9,10,5,5,6,4,12,5,12,7,
7,3,4,12,4,1,8,7,1,6,6,4,11,5,11}

{879651,656980,11,51564,206,420,917584,205,59290,3323,
644,1,13243,84162,154,561242,1,190,10,136901,420623,
353,573129,81,25,133670,72,528049,5,715560,82641,46,
1,527672,923948,1,13}

{5,1829,51302,3026,4,14,5189,3,25289,2,2967,15994,6}

Returns: 157740289

{4,16,0,10,11,21,11,21,20,6,13,10,10,3,20,15,16,9,6,14,13,8,
17,9,2,21,3,4,10,13,5,7,13,1,12,1,3,13,5,21,12,0,19,15,6,0,
5,13,1,8}

{17,1,8,2,1,7,6,12,18,21,7,20,18,7,6,7,17,20,15,10,14,16,2,6,
19,3,19,3,6,18,10,11,10,4,17,13,15,9,15,17,11,16,13,1,19,17,
19,17,10,2}

{327583,4194,990205,481090,868602,722789,547481,738569,188373,
973550,462208,74066,639614,693164,86808,442101,811939,995334,
551737,335601,147231,93330,799032,130164,839277,757103,234057,
909252,415269,945015,715797,549525,581349,130104,493780,553519,
755216,626951,743631,231151,205857,917585,553454,352015,873807,
573520,569698,317228,754891,875856}

{220468,844712,599675,53333,825995,711279,289092,415428,805292,
985205,197039,193974,95433,244829,558762,555423,725065,498922,
519543,4803,305565,61949}

Returns: 64390854062526

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.