I need an algorithm to generate RANDOM graph for Shortest Path Problems but also want it to be STRONG enough.
Difference between en2 and en3, changed 69 character(s)
Hello, Codeforces!↵

<i>Initially</i>, I intended to just generate <b>random graph with random weights</b> but later have been warned that it may have <b>FEW</b> 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 <i>effective</i> 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, <b>X</b> (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:↵
<b>INPUT:</b>↵

```↵
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↵
```↵

<b>OUTPUT:</b>↵

```3```


/predownloaded/44/91/449153afcd30920dc989211ee2f3176834fdc284.png

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Combi 2021-08-19 13:01:10 69
en2 English Combi 2021-08-19 13:00:24 65
en1 English Combi 2021-08-19 12:56:08 2337 Initial revision (published)