PROBLEM LINK
Author: grebnesieh
Tester: krooonal
DIFFICULITY
Medium
PREREQUISITES
Graph, Dijkstra
PROBLEM
Find the shortest path from the starting point to any one of the finish points such that it contains at least one check point.
EXPLANATION
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.
Done.
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:
seen.add(v1)
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).