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

I'm finding an alternate site that contain the problem of http://www.tsinsen.com/ because I cannot sign up and submit.

I thought I could search gg for problem statement and it will suggest the same problem in other site such as:

• https://loj.ac/

• https://uoj.ac/

However, now I can't even get access to what I need because it's always redirecting to log in site whenever I search for any related site.

Do anyone have any idea I can get access to these problem??

REALLY THANKS!!!! :>

Link to problem: https://szkopul.edu.pl/problemset/problem/keHUVGyQb4AmzCAiUYjyPAnC/site/?key=statement

I think that the statement is concise enough so I will not restate it here.

Here is the link to the Polish solution. This problem is in pages 63-68:

https://oi.edu.pl/static/attachment/20110731/oi5.pdf

However, after reading this I still dont get the way to construct the similarity graph in polynomial complexity. Do anyone have an idea or code related to this problem??

You are given a binary weighted graph of n vertices and m edges (n <= 100, m <= n * (n — 1) / 2) . Consider all possible spanning tree, its cost is the xor sum of its edges, ans its cost is added to the final answer.

Input:

n m (n <= 100, m <= n * (n - 1) / 2

u v w (1 <= u < v <= n, w is 0 or 1)

Output:

sum of cost of all spanning tree with mod 1e9 + 7

My current approach stops with using Kirchhoff theorem at some point of the problem but I don't know what be the elements of the Laplacian Matrix.

I hope someone will notice and help me to solve this problem.