PLNTPATH - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

Setter: Prasanna Kumar
Tester: Anshu Garg

DIFFICULTY:

EASY

PREREQUISITES:

Dijkstra

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:

O((E+V)\log V) \approx O(NK\log N)

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

Why are we drawing edges from planets to portals? Instead can we make a graph such that edges are drawn for portals to portals because intra-portal travel is free.