PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
Setter: Prasanna Kumar
Tester: Anshu Garg
DIFFICULTY:
EASY
PREREQUISITES:
PROBLEM:
Given N planets, each belonging to some alliance. C_{i,j} represents the cost to travel from planet i to any planet that belongs to alliance j. Determine the minimum cost to reach every planet from planet S.
EXPLANATION:
Clearly, the problem is a Single Source Shortest Path problem. The trick is to model the graph appropriately.
Naive solution (TLE)
A naive approach would be to draw undirected edges with weight C_{i,j} between planet i and all planets belonging to the alliance j.
Running Dijkstra on this graph will give us the answer. However, the number of edges in the worst case would be N^2, which is too much to run within the time limit.
Construct K portals, one for each alliance, such that portal j will teleport you to any planet in alliance j for free. Let the cost of travelling from planet i to portal j be C_{i,j}.
Now, going from planet u\to planet v - is equivalent to (w.r.t. the travel cost) - going from planet u\to portal A_v\to planet v.
Thus, instead of drawing edges between planets (as in the naive approach), we draw edges from planets to portals, reducing the number of edges to N*K.
Graph construction
Construct N+K nodes, representing planets and portals respectively.
Draw a directed edge with weight 0, from portal A_i to planet i, for all i.
Also draw a directed edge (why not undirected?) from planet i to portal j, with weight C_{i,j}, for all i,j.
Running Dijkstra on this graph will give us the desired answer!
TIME COMPLEXITY:
There are N+K nodes in the graph, with N*K edges in the worst case. The total time complexity of running Dijkstra over the graph is thus:
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters