Submission #559036

#	Time	Username	Problem	Language	Result	Execution time	Memory
559036		jh05013	Price List (POI13_cen)	Pypy 3	0 / 100	442 ms	65536 KiB

cen

from heapq import *
import sys;input=lambda:sys.stdin.readline().strip('\n')
MIS = lambda: map(int,input().split())

n, m, source, c1, c2 = MIS()
adj = [set() for i in range(n+1)]
for i in range(m):
    a, b = MIS()
    adj[a].add(b); adj[b].add(a)

dist = [10**18]*(n+1); dist[source] = 0
PQ = [(0, source)]
while PQ:
    d, u = heappop(PQ)
    if dist[u] != d: continue
    for v in adj[u]:
        # edge type 1
        nd = d+c1
        if dist[v] <= nd: continue
        dist[v] = nd; heappush(PQ, (nd, v))
        # edge type 2
        nd = d+c2
        to_remove = []
        for v2 in adj[v]:
            if v2 in adj[u] or dist[v2] <= nd: continue
            dist[v2] = nd; heappush(PQ, (nd, v2))
            to_remove.append(v2)
        for v2 in to_remove: adj[v].remove(v2)
print(*dist[1:])

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10