32942023-02-24 12:42:4512BotiTom és Jerry2 (60)python3Runtime error 2/60352ms51592 KiB
from collections import deque
from math import inf

N, M, tstart, db, E = map(int, input().split())
tstart -= 1
E -= 1
ns = [[] for _ in range(N)]
for _ in range(M):
    a, b, s = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    ns[a].append((b, s))
    ns[b].append((a, s))
jstarts = [int(x) - 1 for x in input().split()]


treach = [inf] * N
treach[tstart] = 0
q = deque([tstart])
while len(q) > 0:
    n = q.popleft()
    for (ne, s) in ns[n]:
        if s == 2 and treach[ne] == inf and ne != E:
            treach[ne] = treach[n] + 1
            q.append(ne)
ereach = [inf] * N
ereach[E] = 0
q = deque([E])
while len(q) > 0:
    n = q.popleft()
    for (ne, s) in ns[n]:
        if ereach[ne] == inf:
            ereach[ne] = ereach[n] + 1
            q.append(ne)

# print(ns)
# print(treach)
# print(ereach)

par = [None] * N
par[E] = -1
paridx = [None] * N
paridx[E] = -1
order = []


def dfs(n):
    order.append(n)
    for i, (ne, _) in enumerate(ns[n]):
        if par[ne] is not None:
            if par[n] == ne:
                paridx[n] = i
            continue
        par[ne] = n
        dfs(ne)


dfs(E)
# print(par)

bridge = [[True] * len(n) for n in ns]
cutv = [False]*N
firstloop = True
visited = [False] * N
for n in order:
    visited[n] = True
    for i, (ne, _) in enumerate(ns[n]):
        if par[ne] == n or par[n] == ne:
            continue
        # print("chain:")
        bridge[n][i] = False
        while visited[ne] is False:
            # print(ne)
            visited[ne] = True
            # print(ne, paridx[ne])
            bridge[ne][paridx[ne]] = False
            ne = par[ne]
        if ne == n:
            if firstloop:
                firstloop = False
            else:
                cutv[n] = True

for n in range(N):
    if par[n] != -1 and bridge[n][paridx[n]] is True:
        cutv[n] = True
        cutv[par[n]] = True
# print(cutv)
# print(bridge)

score = [treach[n] + ereach[n] if cutv[n] else inf for n in range(N)]
# print(score)
best = list(range(N))
for n in order:
    if par[n] == -1:
        continue
    if score[best[par[n]]] < score[best[n]]:
        best[n] = best[par[n]]
# print(best)

for jstart in jstarts:
    if ereach[jstart] >= score[best[jstart]]:
        print(best[jstart]+1)
    else:
        print(0)
SubtaskSumTestVerdictTimeMemory
base2/60
1Accepted0/021ms12592 KiB
2Runtime error0/085ms21836 KiB
3Accepted2/220ms13212 KiB
4Wrong answer0/220ms13184 KiB
5Wrong answer0/221ms13368 KiB
6Wrong answer0/323ms13748 KiB
7Wrong answer0/225ms13980 KiB
8Wrong answer0/229ms14724 KiB
9Wrong answer0/228ms14884 KiB
10Wrong answer0/332ms15292 KiB
11Wrong answer0/332ms15648 KiB
12Wrong answer0/343ms17324 KiB
13Runtime error0/352ms19656 KiB
14Runtime error0/361ms21012 KiB
15Runtime error0/371ms22108 KiB
16Runtime error0/383ms23012 KiB
17Runtime error0/376ms25408 KiB
18Runtime error0/3138ms34580 KiB
19Runtime error0/4241ms39260 KiB
20Runtime error0/4352ms51592 KiB
21Runtime error0/5189ms42376 KiB
22Runtime error0/5200ms42600 KiB