In order to expand its reach to the outer universe and ensure universal peace, the [MIB] has decided to expand its offices.
Namely, it has established its office on N most important planets in the universe, with the base station on the planet S. Each office has an intergalactic teleporter that connects it to other planet offices. But the teleporters are bound to a planet's policy, so you cannot teleport to any planet you wish.

Due to intergalactic feuds, the planets are divided into K different alliances, numbered 1 through K. You know for each planet i, the alliance that it belongs to. In other words, you're given a sequence A_{1}, A_{2}, \dots, A_{n}, which says that planet i belongs to alliance A_{i}.

Each planet i has a policy of teleportation to the planets of other alliances:
Cost to travel from one planet to another is determined by the alliance of the destination planet. More formally, the cost to reach a planet which belongs to alliance j from planet i is represented as C_{i, j}. 
Intra-alliance travel is free, i.e., if A_{i} = j, then C_{i, j} = 0. 
For a planet i, there are some forbidden alliances as well. For these alliances, C_{i, j} = -1, given that alliance j is forbidden to travel from planet i.

As MIB is bound to follow the intergalactic rules and since they have limited funds (yes, the government is cheap everywhere), they have decided to find the most optimal way to travel to each of the planets from the base station at planet S. With all other agents busy with their missions, you are assigned the task to find these minimum-cost paths. This is your first task in MIB, so don't let them down!

------ Input Format ------ 

- The first line will consist of three space-separated integers N, K, and S (number of planets, number of alliances, and base planet).
- Second-line will consist of N space-separated integers representing A_{i}, the alliance corresponding to the i^{th} planet.
- Each of the next N lines will consist of K space-separated integers, where the j^{th} integer of the i^{th} line represents C_{i, j}, the cost to travel from planet i to alliance j.

------ Output Format ------ 

Print N space separated integers, the i^{th} integer representing the minimal cost to reach the i^{th} planet from the base station. For unreachable planets print -1.

------ Constraints ------ 

$1 ≤ N ≤ 2 * 10^{4}$
$1 ≤ K ≤ min(N, 1000)$
$N * K ≤ 2 * 10^{6}$
$1 ≤ A_{i} ≤ K$
$-1 ≤ C_{i,j} ≤ 10^{9}$

----- Sample Input 1 ------ 
5 3 4
1 3 1 2 2 
0 5 -1 
-1 4 0 
0 3 -1 
4 0 -1 
4 0 3 

----- Sample Output 1 ------ 
4 3 4 0 0 

----- explanation 1 ------ 
- As $4$ and $5$ belong to the same component, the cost of traveling in-between is $0$. 

- There are multiple shortest paths from $4$ to $1$. They are:
$4 \rightarrow 3 \rightarrow 1, 4 \rightarrow 5 \rightarrow 3 \rightarrow 1$, $4 \rightarrow 1$, etc. All of these have equal costs, that is $4$.

- Only path from $4$ to $2$ is $4 \rightarrow 5 \rightarrow 2$, which costs $3$ units.

- Similarly for node $3$, the cost is $4$ units.

Source: codechef | Difficulty: VERY_HARD
Tags: Graph algorithms

Data structures

Shortest paths


Solutions:
import heapq
import math
import collections
(n, k, s) = map(int, input().split())
a = list(map(int, input().split()))
alliance = [list(map(int, input().split())) for _ in range(n)]
planet = collections.defaultdict(list)
for i in range(1, k + 1):
	planet[i] = []
for (i, v) in enumerate(a):
	planet[v].append(i)
heap = [(0, a[s - 1])]
heapq.heapify(heap)
ans = {}
visited = set()
while heap:
	(dist, node) = heapq.heappop(heap)
	if node in visited:
		continue
	ans[node] = dist
	visited.add(node)
	for i in planet[node]:
		for (j, k) in enumerate(alliance[i]):
			if j + 1 not in visited and k != -1:
				heapq.heappush(heap, (k + dist, j + 1))
for i in planet:
	if i not in visited:
		ans[i] = -1
print(*[ans[v] for v in a])


from heapq import *
from collections import defaultdict as dd

def dijsktra(src):
	ans = dd(lambda : 10 ** 10)
	ans[src] = 0
	prcessed = set()
	prcessed.add(src)
	h = []
	heappush(h, [0, src])
	while h:
		(d, node) = heappop(h)
		for v in g[node]:
			if v not in prcessed and d + g[node][v] < ans[v]:
				ans[v] = d + g[node][v]
				heappush(h, [ans[v], v])
		prcessed.add(node)
	return ans
(n, k, s) = map(int, input().split())
a = list(map(int, input().split()))
cost = []
g = dd(dict)
for i in range(n):
	a[i] -= 1
for i in range(n):
	l = list(map(int, input().split()))
	for i in range(k):
		if l[i] == -1:
			l[i] = 10 ** 10
	cost.append(l)
for i in range(n):
	for j in range(k):
		g[a[i]][j] = min(g[a[i]][j], cost[i][j]) if j in g[a[i]] else cost[i][j]
src = a[s - 1]
ans = dijsktra(src)
res = []
for i in range(n):
	res.append(-1 if ans[a[i]] >= 10 ** 10 else ans[a[i]])
print(*res)


import heapq
from collections import defaultdict as dd
g = dd(dict)
inf = 10 ** 100

def dijsktra(src):
	ans = dd(lambda : inf)
	ans[src] = 0
	prcessed = set()
	prcessed.add(src)
	h = []
	heapq.heappush(h, [0, src])
	while len(h):
		(d, node) = heapq.heappop(h)
		for v in g[node]:
			te = d + g[node][v]
			if v not in prcessed and te < ans[v]:
				ans[v] = te
				heapq.heappush(h, [ans[v], v])
		prcessed.add(node)
	return ans
(n, k, s) = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
	a[i] -= 1
cost = []
for i in range(n):
	L = list(map(int, input().split()))
	for i in range(k):
		if L[i] == -1:
			L[i] = inf
	cost.append(L)
for i in range(n):
	for j in range(k):
		if j in g[a[i]]:
			g[a[i]][j] = min(g[a[i]][j], cost[i][j])
		else:
			g[a[i]][j] = cost[i][j]
src = a[s - 1]
ans = dijsktra(src)
pp = ''
for i in range(n):
	if ans[a[i]] >= inf:
		pp += '-1 '
	else:
		pp += str(ans[a[i]]) + ' '
print(pp)


from sys import stdin
input = stdin.readline
import heapq

def answer():
	q = []
	heapq.heappush(q, [0, a[s - 1]])
	allans = [float('inf')] * (k + 1)
	allans[a[s - 1]] = 0
	visited = [False] * (k + 1)
	while len(q):
		(cost, p) = heapq.heappop(q)
		if visited[p]:
			continue
		visited[p] = True
		for i in range(1, k + 1):
			if edges[p][i] == -1 or visited[i]:
				continue
			if cost + edges[p][i] < allans[i]:
				allans[i] = cost + edges[p][i]
				heapq.heappush(q, [allans[i], i])
	for i in range(k + 1):
		if allans[i] == float('inf'):
			allans[i] = -1
	ans = [-1] * (n + 1)
	for i in range(1, k + 1):
		for j in alliance[i]:
			ans[j] = allans[i]
	return ans[1:]
for T in range(1):
	(n, k, s) = map(int, input().split())
	a = list(map(int, input().split()))
	c = [list(map(int, input().split())) for i in range(n)]
	alliance = [[] for i in range(k + 1)]
	for i in range(n):
		alliance[a[i]].append(i + 1)
	edges = [[-1 for i in range(k + 1)] for j in range(k + 1)]
	for x in range(1, k + 1):
		for j in range(1, k + 1):
			m = float('inf')
			for i in alliance[x]:
				if c[i - 1][j - 1] == -1:
					continue
				m = min(m, c[i - 1][j - 1])
			if m == float('inf'):
				m = -1
			edges[x][j] = m
	print(*answer())


(N, K, S) = map(int, input().split())
S -= 1
A = list(map(lambda x: int(x) - 1, input().split()))
C = []
for i in range(N):
	C.append(list(map(int, input().split())))
C_BW_A = [{} for i in range(K)]
for i in range(N):
	a = A[i]
	for b in range(K):
		if a != b:
			cur_c = C_BW_A[a].get(b, float('inf'))
			cost_f_p = C[i][b]
			if 0 <= cost_f_p < cur_c:
				C_BW_A[a][b] = cost_f_p
C_F_BASE = [float('inf') for i in range(K)]
C_F_BASE[A[S]] = 0
unvisited = set(range(K))
while unvisited:
	(min_d, min_a) = (float('inf'), -1)
	for a in unvisited:
		if C_F_BASE[a] < min_d:
			min_d = C_F_BASE[a]
			min_a = a
	if min_a == -1:
		break
	unvisited.remove(min_a)
	for (n, l) in C_BW_A[min_a].items():
		ndist = min_d + l
		if ndist < C_F_BASE[n]:
			C_F_BASE[n] = ndist
for i in range(K):
	if C_F_BASE[i] == float('inf'):
		C_F_BASE[i] = -1
print(' '.join((str(C_F_BASE[A[i]]) for i in range(N))))


from collections import defaultdict
import heapq
(n, k, s) = map(int, input().split())
a = list(map(int, input().split()))
cost = []
dist = [[float('inf') for _ in range(k + 1)] for __ in range(k + 1)]
for j in range(n):
	ca = list(map(int, input().split()))
	for jj in range(1, k + 1):
		if ca[jj - 1] != -1:
			dist[a[j]][jj] = min(dist[a[j]][jj], ca[jj - 1])
adj = defaultdict(list)
for i in range(1, k + 1):
	for j in range(1, k + 1):
		if i != j and dist[i][j] != float('inf'):
			adj[i].append((j, dist[i][j]))
inf = float('inf')
dist = [inf for i in range(k + 1)]
dist[a[s - 1]] = 0
pq = [(0, a[s - 1])]
while pq:
	(wei, node) = heapq.heappop(pq)
	for (cnode, cw) in adj[node]:
		cdis = wei + cw
		if cdis < dist[cnode]:
			dist[cnode] = cdis
			heapq.heappush(pq, (cdis, cnode))
for i in range(n):
	grp = a[i]
	ans = dist[grp]
	if ans == float('inf'):
		ans = -1
	print(ans, end=' ')
print()


import heapq
import sys
input = sys.stdin.readline
(n, k, s) = map(int, input().split())
(a, pl_al) = (list(map(int, input().split())), {i: [] for i in range(1, k + 1)})
for (i, v) in enumerate(a):
	pl_al[v].append(i)
c = [list(map(int, input().split())) for _ in range(n)]
(heap, costs) = ([(0, a[s - 1])], {})
while heap:
	(cost, al) = heapq.heappop(heap)
	if al in costs:
		continue
	costs[al] = cost
	for pl in pl_al[al]:
		for (i, v) in enumerate(c[pl]):
			if i + 1 not in costs and v != -1:
				heapq.heappush(heap, (cost + v, i + 1))
for v in pl_al:
	if v not in costs:
		costs[v] = -1
print(' '.join((str(costs[v]) for v in a)))