76 lines
1.6 KiB
Python
76 lines
1.6 KiB
Python
"""PARTIEL BUG"""
|
|
from collections import defaultdict
|
|
import heapq
|
|
|
|
class Graph:
|
|
def __init__(self, n):
|
|
self.graph = defaultdict(list)
|
|
self.n = n
|
|
self.seats = None
|
|
|
|
def set_seats(self, seats, n):
|
|
self.seats = [(i in seats) for i in range(n)]
|
|
|
|
def add_edge(self, u, v, weight=1):
|
|
self.graph[u].append((weight, v))
|
|
|
|
def bfs(self, s):
|
|
heap = []
|
|
|
|
visited = [False] * (self.n + 1)
|
|
|
|
heapq.heappush(heap, (0, s))
|
|
visited[s] = True
|
|
|
|
while heap:
|
|
prio, s = heapq.heappop(heap)
|
|
if self.seats[s]:
|
|
return prio
|
|
|
|
for w, v in self.graph[s]:
|
|
if not visited[v]:
|
|
heapq.heappush(heap, (w+prio, v))
|
|
visited[v] = True
|
|
|
|
return float("inf")
|
|
|
|
def main():
|
|
# nb of seats, V, E
|
|
k, n, m = map(int, input().split())
|
|
|
|
# Prepare Graph
|
|
students = [int(i)-1 for i in input().split()]
|
|
seats = [int(i)-1 for i in input().split()]
|
|
|
|
g = Graph(n)
|
|
g.set_seats(seats, n)
|
|
|
|
for i in range(m):
|
|
a, b, c = input().split()
|
|
g.add_edge(int(a)-1, int(b)-1, weight=int(c))
|
|
|
|
|
|
# BFS from each of the students to determine the fastest
|
|
dists = []
|
|
for st in students:
|
|
dists.append(g.bfs(st))
|
|
|
|
mini = float("inf")
|
|
best = -1
|
|
for i in range(k):
|
|
if dists[i] < mini:
|
|
mini = dists[i]
|
|
best = i
|
|
elif dists[i] == mini:
|
|
return "impossible"
|
|
|
|
if best == -1:
|
|
return "impossible"
|
|
|
|
return students[best]+1
|
|
|
|
|
|
|
|
|
|
for _ in range(int(input())):
|
|
print(main()) |