QUCOCYL - Editorial




Author: grebnesieh

Tester: krooonal




Graph, Dijkstra


Find the shortest path from the starting point to any one of the finish points such that it contains at least one check point.


This question as well was pretty simple in implementation, Dijkstra’s algorithm.

Just figuring out how to do it was the hard part.

The simplest way to do it that I found is to run the algorithm on the root node once and obtain the shortest distance from the root node to all others.

Then you can insert an extra node and connect it to all the checkpoints with an edge weight of their shortest distance from the root.

Run djikstra on the extra node, and take the minimum of the shortest distance of the extra node to all the finish points.


An implementation of djikstra with a heap or priority queue can be easily found online, here is one in python:

from collections import defaultdict
from heapq import *
def dijkstra(s):
    q, seen = [(0,s)], set()
    while q:
        cost, v1 = heappop(q)
        if v1 not in seen:
            shortestDistance[v1] = cost
            for c, v2 in g[v1]:
                if v2 not in seen:
                    heappush(q, (cost+c, v2))

The remaining code is as follows:

N, M, C, F = map(int, raw_input().split())
g = [[] for i in xrange(N)]
shortestDistance = [-1 for i in xrange(N)]
checks = map(int, raw_input().split())
finish = map(int, raw_input().split())
for _ in xrange(M):
    source, destination, distance = map(int, raw_input().split())
    g[source].append((distance, destination))

shortestDistance = [-1 for i in xrange(N)]
dijkstra(0)                                                         # first dijkstra

g.append([])                                                        # extra node

for x in checks:
    if shortestDistance[x] >= 0:
        g[N].append((shortestDistance[x], x))

shortestDistance = [-1 for i in xrange(N + 1)]
dijkstra(N)                                                         # second dijkstra

ans = 10 ** 20

for x in finish:
    if shortestDistance[x] >= 0:
        ans = min(ans, shortestDistance[x])

print ans

The complexity is O(M logN).


@grebnesieh didnt thought of the solution , saw many submissions taking help of DP to solve it can u xplain it ?

@adijimmy All AC solutions I have seen have used Dijkstra. Can you point one out to me that doesn’t? (I will have a looksie in the morning though.)

I have a different logic. What i did was run dijkstra’s to get the shortest distance from each vertex from source. Then i looped through all the checkpoints assuming that one of them would be in the required shortest path. For each checkpoint i check if (the distance to this checkpoint from source) + (if a finish node is directly connected to it then the weight edge between this point and the finish point) is smaller than the current answer, then update the current answer. This was done with the assumption that the checkpoint should be directly connected to the finishing point if it is connected through another checkpoint, then it will be taken care of when we process that checkpoint. As a special case if it is connected to 0, for that I had already stored the smallest weighing finish point directly connected to 0.
I got a WA with the above mentioned logic, here is my code, which is working on sample case though.

If you find any bug in my code or logic then please help.

can u please add it to the practice session

I have a solution that does not use dijkstra, at least not explicitly (had never heard of it). I would describe it as cross of a breadth-first search and a best-edge algorithm. Start by following edge of least weight. Note end-node and total travel distance, and if checkpoint has been reached. Store in list. Remove edge. Now iterate, looking for least total weight moving from any visited node.

I was not able to compete but think I have solutions to all problems. Could we have these up in the practice room? Thanks so much! Appreciate you writing your solutions in Python!!!

What you have described, if I understand correctly is Dijkstra (with priority queue). Try to implement what is in your mind first, then, regardless of whether it works or not, read up on Dijkstra and try to implement that as well. :slight_smile:

As for the practice room, I don’t have access for that, waiting on the codechef guys to do it.

And you’re welcome for the Python code. xD I use it all the time and I feel it does make sense to use it in editorials, it is pretty much like pseudocode which you can execute and test as well.