[백준 17396] 백도어
1. 문제 설명
2. 문제 분석
다익스트라에서 업데이트하는 노드 코스트에 조건을 하나 더 추가한다.
3. 나의 풀이
import sys
import heapq
n, m = map(int, sys.stdin.readline().rstrip().split())
visible = list(map(int, sys.stdin.readline().rstrip().split()))
INF = sys.maxsize
nodes= [[] for _ in range(n)]
for _ in range(m):
a, b, t = map(int, sys.stdin.readline().rstrip().split())
nodes[a].append([b, t])
nodes[b].append([a, t])
def Dijkstra():
distances = [INF for _ in range(n)]
distances[0] = 0
pq = []
heapq.heappush(pq, [0, 0])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if next_node != n-1:
if visible[next_node] == 0 and distances[next_node] > next_cost + cur_cost:
distances[next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
else:
if distances[next_node] > next_cost + cur_cost:
distances[next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
if distances[n-1] == INF: return -1
else: return distances[n-1]
print(Dijkstra())
Author And Source
이 문제에 관하여([백준 17396] 백도어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-17396-백도어
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
다익스트라에서 업데이트하는 노드 코스트에 조건을 하나 더 추가한다.
3. 나의 풀이
import sys
import heapq
n, m = map(int, sys.stdin.readline().rstrip().split())
visible = list(map(int, sys.stdin.readline().rstrip().split()))
INF = sys.maxsize
nodes= [[] for _ in range(n)]
for _ in range(m):
a, b, t = map(int, sys.stdin.readline().rstrip().split())
nodes[a].append([b, t])
nodes[b].append([a, t])
def Dijkstra():
distances = [INF for _ in range(n)]
distances[0] = 0
pq = []
heapq.heappush(pq, [0, 0])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if next_node != n-1:
if visible[next_node] == 0 and distances[next_node] > next_cost + cur_cost:
distances[next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
else:
if distances[next_node] > next_cost + cur_cost:
distances[next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
if distances[n-1] == INF: return -1
else: return distances[n-1]
print(Dijkstra())
Author And Source
이 문제에 관하여([백준 17396] 백도어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-17396-백도어
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
import heapq
n, m = map(int, sys.stdin.readline().rstrip().split())
visible = list(map(int, sys.stdin.readline().rstrip().split()))
INF = sys.maxsize
nodes= [[] for _ in range(n)]
for _ in range(m):
a, b, t = map(int, sys.stdin.readline().rstrip().split())
nodes[a].append([b, t])
nodes[b].append([a, t])
def Dijkstra():
distances = [INF for _ in range(n)]
distances[0] = 0
pq = []
heapq.heappush(pq, [0, 0])
while pq:
cur_cost, cur_node = heapq.heappop(pq)
if distances[cur_node] < cur_cost: continue
for next_node, next_cost in nodes[cur_node]:
if next_node != n-1:
if visible[next_node] == 0 and distances[next_node] > next_cost + cur_cost:
distances[next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
else:
if distances[next_node] > next_cost + cur_cost:
distances[next_node] = next_cost + cur_cost
heapq.heappush(pq, [next_cost + cur_cost, next_node])
if distances[n-1] == INF: return -1
else: return distances[n-1]
print(Dijkstra())
Author And Source
이 문제에 관하여([백준 17396] 백도어), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@j_aion/백준-17396-백도어저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)