oj.uz

답안 #559037

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559037 2022-05-09T09:51:29 Z jh05013 Price List (POI13_cen) PyPy 3
0 / 100
 376 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)]
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: continue
        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:])

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 18220 KB Output is correct
2 Correct 38 ms 18260 KB Output is correct
3 Correct 37 ms 18232 KB Output is correct
4 Incorrect 36 ms 18316 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 18228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 70 ms 20420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 199 ms 33460 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 376 ms 52676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 299 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 288 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 295 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 281 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 296 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -