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