oj.uz

답안 #559048

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
559048 2022-05-09T10:05:26 Z jh05013 Price List (POI13_cen) PyPy 3
50 / 100
 497 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:
            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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 18220 KB Output is correct
2 Correct 40 ms 18256 KB Output is correct
3 Correct 41 ms 18220 KB Output is correct
4 Correct 52 ms 18308 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 18260 KB Output is correct
2 Correct 41 ms 18316 KB Output is correct
3 Correct 44 ms 18292 KB Output is correct
4 Correct 42 ms 18412 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 20668 KB Output is correct
2 Correct 74 ms 21088 KB Output is correct
3 Correct 75 ms 20908 KB Output is correct
4 Correct 70 ms 20224 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 223 ms 35456 KB Output is correct
2 Correct 199 ms 32148 KB Output is correct
3 Correct 326 ms 35752 KB Output is correct
4 Correct 227 ms 34032 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 54040 KB Output is correct
2 Correct 351 ms 52340 KB Output is correct
3 Correct 497 ms 52424 KB Output is correct
4 Correct 422 ms 52300 KB Output is correct

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 318 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 292 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -