# CHEFCCYL - Editorial

Ah, I could have used the [hid e][/h ide] function if I knew it earlier. This would make editorials clearer, I think.

Practice

Contest

Author: Full name

Tester: Full name

Editorialist: Full name

### DIFFICULTY:

CAKEWALK, SIMPLE, EASY, MEDIUM or HARD.
Intermediate levels like SIMPLE-EASY, EASY-MEDIUM, MEDIUM-HARD are also possible.

### PREREQUISITES:

Greedy, DP, Math etc. Ideally with the links to Wikipedia

### PROBLEM:

Click to view

There are N cycles(some kind of weighted undirected graphs) and N additional edges. The i-th additional edge connects some node on the i-th cycle and some node on the (i+1)-th cycle. Specially, the N-th additional edge connects some node on the N-th cycle and som node on the 1-st cycle. Every edge has a weight. You need to answer Q queries, each query asks you the length of the shortest path between some two nodes.

### QUICK EXPLANATION:

Let’s call the endpoints of additional edges "keypoint"s. The topology of keypoints form a cycle, so we can handle distance queries of keypoints quickly. For a general query, let’s say it’s from vertex v_1 on cycle c_1 to vertex v_2 on cycle c_2. The path goes through some keypoint k_1 on cycle c_1 and some k_2 on cycle c_2. Since every cycle has at most 2 keypoints, we enumerate k_1 and k_2, and thus answer queries on constant time.

### EXPLANATION:

This is a shortest path problem on a graph with M=A_1+A_2+\dots+A_N vertices and M+1 edges. We can run Dijkstra’s Algorithm for each query. The time complexity for heap-optimized Dijkstra’s Algorithm is O(M\log M). So total complexity is O(QM\log M).

### Querying on one cycle

Consider the easier problem: you have one cycle and you want to answer distance queries. Let’s number the vertices 1,2,\dots,N, and suppose the cycle is 1-2-3-\dots-N-1. For any i,j(i < j), the only simple paths between i,j are:

• i\to (i+1)\to(i+2)\to\dots\to j, length l_1;
• i\to (i-1)\to\dots\to 1\to N\to (N-1)\to\dots\to (j+1)\to j, length l_2.

Let’s precompute d_i as the length of path 1\to 2\to\dots\to i. Then l_1=d_j-d_i. Since l_2+l_1 is the length of the whole cycle, l_2 can be easily calculated, too. We return the smaller number between l_1 and l_2, and answer the query in O(1) time.

### Querying on keypoints

Let’s call the endpoints of additional edges "keypoint"s. Consider how to answer distance queries between keypoints. We construct a new graph C whose vertices are only the keypoints. For two keypoints:

• if they are connected by an additional edge, we add this edge to C;
• if they are in the same cycle, we query that cycle and get their distance d in the cycle, then connect them with an edge of weight d.

The resulting graph C is a cycle: every vertex has degree 2 and C is connected. Thus we can easily handle distance queries on C. Also, C preserves distances on the original graph. So we can answer distance queries about endpoints in O(1) time.

### The final solution

First, using the above algorithms we can support distance queries on one cycle and on keypoints.

Suppose there is a query (V_1,C_1,V_2,C_2). Since C_1\ne C_2, their shortest path must pass through some keypoint in cycle C_1, suppose it’s k_1; it also passes through some keypoint in cycle C_2, say k_2. Then the shortest path has length dis(V_1,k_1)+dis(k_1,k_2)+dis(k_2,V_2), and the smallest this value among all (k_1,k_2)'s is the answer. The three dis()'s can be obtained in O(1) time. Each cycle has at most 2 keypoints, so there are at most 4 pairs of (k_1,k_2) that we need to enumerate.

The time complexity is O(Q+M), where M=A_1+A_2+\dots+A_N.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found [here][333].
Tester’s solution can be found [here][444].

### RELATED PROBLEMS:

[333]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server.
[444]: The link is provided by admins after the contest ends and the solutions are uploaded on the CodeChef Server