Submission #559053

#	Time	Username	Problem	Language	Result	Execution time	Memory
559053		jh05013	Price List (POI13_cen)	Cpython 3	40 / 100	4097 ms	65276 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)]
adj2 = [set() for i in range(n+1)]
for i in range(m):
    a, b = MIS()
    adj[a].add(b); adj[b].add(a)
    adj2[a].add(b); adj2[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:
            dist[v] = nd; heappush(PQ, (nd, v))
        # edge type 2
        nd = d+c2
        to_remove = []
        for v2 in adj2[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: adj2[v].remove(v2)
print(*dist[1:], sep='\n')

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 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