Hello, Codeforces!

Initially, I intended to just generate random graph with random weights but later have been warned that it may have FEW number of shortest Path and the contestants can random one of those shortest Path and solve the problems.

(Of course it cannot be allowed to pass all the test). So I wanna ask for some effective algorithm to generate test for this problems. Btw I do not know how tests for such problems are generated in the pass.

If you are interested, I will specify the problems:

Statement

There is a connected graph with $$$n$$$ vertices and $$$m$$$ edges ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$).

There are also $$$K (1 \leq K \leq 10)$$$ pairs of vertices $$$a_i$$$ and $$$b_i (1 \leq a_i, b_i \leq n)$$$ in which: - $$$a_i$$$ is the node which the $$$i-th$$$ person lives in. - $$$b_i$$$ is the node which the $$$i-th$$$ person's office located in.

Every morning, $$$i-th$$$ goes to work form home at 7AM along the shortest path connected $$$a_i$$$ and $$$b_i$$$. However, X (the first person) want to walk together with one of $$$K - 1$$$ other people during his path.

Two people are considered walking together on the edges form u to v, if: - both u and v are on the both shortest path that these 2 people walking on - the time at which 2 people reach u and v is the same.

Furthermore, some of these people (except X) agree to start walking later or sooner form home so that the time X walking together with at least one of other person is as large as possible.

The target of this problems is maximizing the amount oft time X walking with one of other people during his path form home to office.

INPUT:

• The first line contains 3 integer $$$n, m, K (1 \leq n, m \leq 10^5, 1 \leq K \leq 10)$$$
• The next m lines have the form of $$$u, v, c$$$ ($$$u$$$ and $$$v$$$ is the end of edge, $$$1 \leq c \leq 10^9$$$ is the time required to pass)
• The next K lines have the form of $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$)

OUTPUT:

The largest amount of time in which X walk together with one of $$$K - 1$$$ other people.

Example:

INPUT:

7 8 4
2 1 2
2 4 2
4 3 2
4 5 1
1 5 3
1 7 3
5 6 2
7 6 8
1 4
0 3 2
1 7 6
0 1 2

OUTPUT:

3

/predownloaded/44/91/449153afcd30920dc989211ee2f3176834fdc284.png