You are not logged in. Please login at www.codechef.com to post your questions!

×

easy

# PREREQUISITES

graph theory, Dijkstra's algorithm, transforming graph into similar graph

# PROBLEM

You are given a undirected weighted graph consisting of $n$ vertices, and $m$ edges. Initially there is no edge between any pair of first $K$ vertices. We add the edge between each pair of first $K$ vertices of weight $X$ (i.e. the first $K$ vertices form a clique). Given a source vertex $s$, find out the shortest distance of each node from vertex $s$.

Finding the shortest distance in a weighted graph from a fixed source vertex is a classical problem. There is a famous greedy algorithm called Dijkstra's algorithm which can solve this problem in $\mathcal{O}((|V| + E|) log (|V|))$ time.

If we directly apply the Dijkstra's algorithm in our problem, the number of vertices, i.e. $|V| = n$, and the number of edges, i.e. $|E| = m$ + $\binom{K}{2}$ (due to the clique). Hence, the time complexity of this algorithm will be $\mathcal{O}((m + K^2) \, log (n))$, which is enough to solve the first subtask, but won't be sufficient to solve the final subtask.

# Solution by constructing another graph

One of the ways of dealing with such situations is to think whether it is possible to convert the given graph into another graph that doesn't have $\mathcal{O}(K^2)$ edges of the clique added in it, and yet it preserves the pairwise distances of the vertices of the original graph.

We can do this in the following way. Let us create a fake vertex. This fake vertex will be connected to the each of the first $K$ vertices. The weight of each edge will be $\frac{X}{2}$. So now, instead of the first $K$ vertices being connected in the form of clique are connected to the fake vertex in the form of a star topology where the central node of star is the fake vertex.

// Add an image.

Thus we have $K$ edges in the modified graph instead of $K^2$ edges of the original graph. The remaining edges in the modified graph will remain same. Notice that the distances in the modified graph are precisely the same as that of in the old graph. Here the edge connecting vertices $u$ and $v$ (where $u, v \leq K$) with weight $X$ directly has been replaced with the $u$ being connected with fake vertex with distance $\frac{X}{2}$, and from the fake vertex with $v$ with distance $\frac{X}{2}$.

Apply Dijkstra's algorithm on this modified graph will yield a time complexity of $\mathcal{O}((m + K) log (n))$ which will give you full score.

A small detail which can be useful here. As the number $\frac{X}{2}$ will not be an integer when $X$ is odd. So, instead of dealing with non-integers (reals) in the Dijkstra's algorithm, you can multiply all the distances by $2$ to make all the distances even. Finally you divide the final distances by 2 to get the actual answer. In this way, you will never have to deal with real numbers.

## Solution by applying the usual Dijkstra with a little twist

You can apply the usual Dijkstra's algorithm. Let $d[i]$ denote the distance of vertex $i$ from source vertex $s$. When you are first time processing one of the vertices belonging to the clique, say vertex $u$, you consider the distances of all other vertices in the clique to be $d[u] + X$. Afterwards, whenever you encounter a vertex in clique, you need not to go over the clique edges to relax the distances of clique vertices. This algorithm will make sure that your time complexity is $\mathcal{O}((m + K) log (n))$, as instead of processing all the $K^2$ edges of clique, you are processing only $K$ of them.

## A solution by trusting your intuition and implement direct Dijkstra with a bit modification.

One might intuitively think that the number of relaxations in the Dijkstra's algorithm might be $m + K$ instead of $m + K^2$. Proof of this intuition lies in the understanding of previous algorithm.

You can directly implement this algorithm. You maintain a set (balanced binary search tree) of the clique vertices sorted by their distances in the increasing order. You can find the set of vertices to relax by making a search in the set. This way, you will only be relaxing the vertices only among the necessary vertices in the clique. See the editorialist's solution for a sample implementation of this approach.

Setter

# TESTER'S SOLUTION

This question is marked "community wiki".

asked 15 Apr '17, 22:09

2.5k52136170
accept rate: 20%

0★admin ♦♦
19.7k350498541

14 Answers:
 4 The naive(TLE) solution would be:  for(i=1;i
 1 Hi @abhishel. Here is the link to my code with comments. Tell if you want any furthur explanation. answered 18 May '17, 11:21 61●1 accept rate: 0%
 0 I figured it out :-). I didn't use faster I/O so I got TLE. answered 17 Apr '17, 16:59 31●3 accept rate: 0%
 0 can anyone please tell me why i am getting wrong ans in second task?? https://www.codechef.com/viewsolution/13274717 answered 17 Apr '17, 19:22 2★sid9406 1●1 accept rate: 0%
 0 Can't access solution files! answered 17 Apr '17, 21:12 1.1k●13 accept rate: 20%
 0 I solved this problem with a trick. Initially I didn't insert the edges of the clique in the edge list. While I am executing the Dijkstra part whenever I am getting a node from the heap which is less than or equal to K, I am doing the following step. Step : Inserting its adjacent edges which connects to the rest vertices in the clique in the edge list and then performing normal Dijkstra. And I am doing this operation only for this node and the next node which is less than or equal to K i.e. if I encounter node which is less than or equal to K but previously I had visited 2 nodes which were less than or equal to K then I am performing normal Dijkstra. this P.S I noticed this pattern of visiting the clique part twice after applying Dijkstra on many graphs with cliques. answered 17 Apr '17, 22:40 3★dybbuk 47●3 accept rate: 20% Your "trick" is what the intended solution is! But instead of 2, visiting just 1 node in the initial K nodes in sufficient. Your code with "cli < 2" changed to "cli < 1" also passes: https://www.codechef.com/viewsolution/13353308 (18 Apr '17, 03:29) drajingo4★
 0 My logic/algo for the question is correct but couldn't get AC in contest. After contest saw the solution of one of my senior :this The logic/algo is same just data structures differ he used set,I used priority_queue in dijkstra and some minor differences.I changed my code too but couldn't get AC. But I am getting TLE for second subtask and WA for the first subtask. Can anyone spot a bug? Thanks! Referenced solution:here My Solution: here answered 17 Apr '17, 23:15 19●3 accept rate: 0%
 0 Can't download or access the solution files answered 18 Apr '17, 03:03 1 accept rate: 0%
 0 I approached the problem with the way: "Solution by applying the usual Dijkstra with a little twist" but unable to get AC ,can't figure out ,how do I do d[u]+X because: Note: I didn't connect 1 to k nodes with X. 1)Now do dijkstra(s) ,but since cliqued ones are not connected yet,so how do I connect these nodes so that I can get d[u]+X ? answered 18 Apr '17, 19:18 62●1 accept rate: 0%
 0 i approached the problem using simple dijkstra algoithm by connecting all adjacent pair in clique getting tle in second subtask which is fine but for first subtask it gives WA for second testcase ,first is AC .cant able to find bug code link->link text link This answer is marked "community wiki". answered 18 Apr '17, 23:09 3★ajaman13 1 accept rate: 0%
 0 The approach I used was: If S <= K, then I will add the new edges from S to all the other K-1 vertices. Then I will do a dijkstra. If S > K, then I will find that node in [1,K] that is closest to S. Then I will add new edges from that node to the remaining K-1 nodes. After that I will do a dijkstra. Intuitively, I was convinced this would work and came up with some kind of a proof in my mind. But it was giving wrong answer for some subtasks. I tried a lot of test cases and they all worked. Could someone tell me whats wrong with the logic? answered 19 Apr '17, 11:54 1 accept rate: 0% I too did the same thing but I had mistaken by calculating these shortest distance after dijkstra's algorithm got implemented. PS probably you have done same mistake as mine or you haven't considered the long long to calculate the result (30 Apr '17, 06:15)
 0 @qruiger_116 While inserting the line adj_list[z].push_back(make_pair(i,0)); should be adj_list[z].push_back(make_pair(i,x)); You should insert the same value of weight and not zero as the weight otherwise it gives wrong answer. answered 29 Apr '17, 22:53 61●1 accept rate: 0% Please read the comment and the visualization properly. I am creating a fake node and I need to keep the cost of travelling from one node to another node(within 1 to k) only as x. Example:(refer the visualiztion) Suppose, I need to go from node 1 to 4 I will take the path 1->6->4 The cost will be 100+0=100 another example, I need to go from node 2 to 3 I will take the path 2->6->3 The cost of this also will be 100+0=100 You can try this for all the other nodes within 1 to k, the cost will always be x. I hope I am clear. Refer this. https://www.codechef.com/viewsolution/13340804 (29 Apr '17, 23:12)
 0 Hi @qruiger_116. I checked your code. My mistake. Putting edge weight as 0 worked for you. But for me it was calculating wrong answers. My logic is same as yours only. My code link : https://www.codechef.com/viewsolution/13413386 Can you tell me one more thing. My second last solution gave wrong answer (partially correct) as I was keeping long long int for the distance only. But in my last solution I changed all variables to long long int and it got accepted how ?? My second last solution link : https://www.codechef.com/viewsolution/13413156 My last solution link : https://www.codechef.com/viewsolution/13413386 answered 29 Apr '17, 23:52 61●1 accept rate: 0%
 0 I understand the logic of fake node but i am unable to code it down and unable to understand other's code can anyone post there code with comment on it, trying to do is question for like 3-4 days. answered 17 May '17, 01:53 2★abhishel 38●3 accept rate: 10%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,477
×3,704
×173
×122
×26

question asked: 15 Apr '17, 22:09

question was seen: 3,844 times

last updated: 05 Aug '17, 13:22