oj.uz

Submission #559036

# Submission time Handle Problem Language Result Execution time Memory
559036 2022-05-09T09:50:21 Z jh05013 Price List (POI13_cen) PyPy 3
0 / 100
 442 ms 65536 KB 
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.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 18276 KB Output is correct
2 Incorrect 41 ms 18300 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 18228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 19392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 228 ms 29772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 273 ms 44336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 364 ms 54748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 431 ms 62188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 439 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 442 ms 62444 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 421 ms 62152 KB Output isn't correct
2 Halted 0 ms 0 KB -