Minimize the delivery time

★★★★★

2.3

18 votes

Graph, Hard, Algorithms, Shortest path problem

Details

Submissions

Discussion

Editorial

Problem

Problem updated (please see Output section)

A company aimed at becoming the first company that solved the MDT problem for factories and restaurants. The MDT problem is easy to explain in an undirected connected graph. Find $k$ vertex-disjoint (excluding 1, n that will appear in every path) simple paths from 1 to $n$ . If the maximum length of these paths is denoted by $M$ , then minimize $\frac{M}{k}$ .

Input format

First line: Two space-separated integers $n$ $(1 \leq n \leq 100\ 000)$ and $m$ $(1 \leq m \le 300\ 000)$
Next $m$ lines: Contains the edges, one edge per line

Output format

First line: Print $k$ ( $k > 0$ ) denoting the number of paths
Next line: Print $k$ lines (one path per line)
For each path, print the number of edges on it and then print the edges in the order.

Verdict, scoring, and test generation plan

You can find all the information here.

Sample Input

Sample Output

2
1 10
2 1 4

Time Limit: 3

Memory Limit: 256

Source Limit:

Explanation

$Score = 48116$ .

Note that choosing $k=1$ and $paths = \{\{10\}\}$ will obtain a less score ( $7027$ ) which is better.

Contributers:

Amirreza Poorakhavan