32952023-02-24 12:42:4712BotiTom és Jerry2 (60)python3Runtime error 2/60393ms51696 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/020ms12716 KiB
2Runtime error0/085ms21880 KiB
3Accepted2/220ms13396 KiB
4Wrong answer0/221ms13640 KiB
5Wrong answer0/221ms13892 KiB
6Wrong answer0/321ms13952 KiB
7Wrong answer0/223ms13888 KiB
8Wrong answer0/228ms14744 KiB
9Wrong answer0/226ms14624 KiB
10Wrong answer0/332ms15324 KiB
11Wrong answer0/332ms15896 KiB
12Wrong answer0/343ms17252 KiB
13Runtime error0/352ms19692 KiB
14Runtime error0/361ms20788 KiB
15Runtime error0/371ms21892 KiB
16Runtime error0/382ms22952 KiB
17Runtime error0/376ms25120 KiB
18Runtime error0/3131ms34068 KiB
19Runtime error0/4230ms38756 KiB
20Runtime error0/4393ms51696 KiB
21Runtime error0/5196ms43384 KiB
22Runtime error0/5196ms42684 KiB