반응형
백준 16118번 달빛 여우
2021.04.15 00:39 기준으로 Python 3 로 통과했는데 시간이 아슬아슬하네요. 새벽이라 서버가 널널해서 통과한 거 같네요. 그래서 다른 코드는 어떻게 통과했나 보려했더니 통과한 코드가 없다?
from heapq import heappush, heappop
import sys
rl = sys.stdin.readline
INF = int(1e9)
def dik_fox():
dist = [INF for _ in range(N+1)]
dist[1] = 0
q = []
heappush(q, (dist[1], 1))
while q:
cd, ci = heappop(q)
if dist[ci] < cd:
continue
for vd, vi in G[ci]:
nd = cd + vd
if nd < dist[vi]:
dist[vi] = nd
heappush(q, (dist[vi], vi))
return dist
def dik_wolf():
# dist[0] 빠르게 도착 / dist[1] 느리게 도착
dist = [[INF] * (N+1) for _ in range(2)]
dist[1][1] = 0
q = []
heappush(q, (dist[1][1], 1, False))
while q:
cd, ci, cf = heappop(q)
if cf and dist[0][ci] < cd:
continue
elif not cf and dist[1][ci] < cd:
continue
for vd, vi in G[ci]:
if cf: # 빠르게 도착했다면, 느리게 출발
nd = cd + (vd * 2)
if nd < dist[1][vi]:
dist[1][vi] = nd
heappush(q, (dist[1][vi], vi, False))
else: # 느리게 도착했다면, 빠르게 출발
nd = cd + (vd // 2)
if nd < dist[0][vi]:
dist[0][vi] = nd
heappush(q, (dist[0][vi], vi, True))
return dist
N, M = map(int, rl().split())
G = [[] for _ in range(N+1)]
for _ in range(M):
a, b, d = map(int, rl().split())
G[a].append((d * 2, b))
G[b].append((d * 2, a))
fox = dik_fox()
wolf = dik_wolf()
answer = 0
for i in range(1, N+1):
if fox[i] < min(wolf[0][i], wolf[1][i]):
answer += 1
print(answer)
TC
5 6
1 2 3
1 3 2
2 3 2
2 4 4
3 5 4
4 5 3
1
--
5 4
1 2 1
2 3 1
3 4 1
4 5 1
2
--
5 5
1 2 1
2 3 1
3 4 1
4 5 2
1 4 3
2
--
5 5
1 2 1
1 4 1
4 5 1
5 1 1
2 3 100
0
--
반응형
'Develop > 코딩인터뷰' 카테고리의 다른 글
[코딩인터뷰] 백준 15683번 감시 (0) | 2021.05.07 |
---|---|
[코딩인터뷰] 2020 카카오 신입 공채 - 문자열 압축 (0) | 2021.04.04 |
[코딩인터뷰] 2020 카카오 신입 공채 - 자물쇠와 열쇠 (0) | 2021.04.04 |
[코딩인터뷰] 백준 2110번 공유기 설치 (0) | 2021.03.30 |
[코딩인터뷰] 백준 10986번 나머지 합 (0) | 2021.03.29 |
꾸준히 노력하는 개발자 "김예건" 입니다.