π Problem Solving/μ΄μ·¨μ½
λ¬Έμ
μ΄λ€ λλΌμλ Nκ°μ λμκ° μλ€. κ·Έλ¦¬κ³ κ° λμλ 보λ΄κ³ μ νλ λ©μμ§κ° μλ κ²½μ°, λ€λ₯Έ λμλ‘ μ 보λ₯Ό 보λ΄μ λ€λ₯Έ λμλ‘ ν΄λΉ λ©μμ§λ₯Ό μ μ‘ν μ μλ€. νμ§λ§ XλΌλ λμμμ YλΌλ λμλ‘ μ 보λ₯Ό 보λ΄κ³ μ νλ€λ©΄, λμ Xμμ Yλ‘ ν₯νλ ν΅λ‘κ° μ€μΉλμ΄ μμ΄μΌ νλ€. μλ₯Ό λ€μ΄ Xμμ Yλ‘ ν₯νλ ν΅λ‘λ μμ§λ§, Yμμ Xλ‘ ν₯νλ ν΅λ‘κ° μλ€λ©΄ Yλ Xλ‘ λ©μμ§λ₯Ό λ³΄λΌ μ μλ€. λν ν΅λ‘λ₯Ό κ±°μ³ λ©μμ§λ₯Ό λ³΄λΌ λλ μΌμ μκ°μ΄ μμλλ€.
μ΄λ λ CλΌλ λμμμ μκΈ μν©μ΄ λ°μνλ€. κ·Έλμ μ΅λν λ§μ λμλ‘ λ©μμ§λ₯Ό 보λ΄κ³ μ νλ€. λ©μμ§λ λμ Cμμ μΆλ°νμ¬ κ° λμ μ¬μ΄μ μ€μΉλ ν΅λ‘λ₯Ό κ±°μ³, μ΅λν λ§μ΄ νΌμ Έλκ° κ²μ΄λ€. κ° λμμ λ²νΈμ ν΅λ‘κ° μ€μΉλμ΄ μλ μ λ³΄κ° μ£Όμ΄μ‘μ λ, λμ Cμμ λ³΄λΈ λ©μμ§λ₯Ό λ°κ² λλ λμμ κ°μλ μ΄ λͺ κ°μ΄λ©° λμλ€μ΄ λͺ¨λ λ©μμ§λ₯Ό λ°λ λ°κΉμ§ 걸리λ μκ°μ μΌλ§μΈμ§ κ³μ°νλ νλ‘κ·Έλ¨μ μμ±νμμ€.
μ λ ₯쑰건
1. 첫째 μ€μ λμμ κ°μ N, ν΅λ‘μ κ°μ M, λ©μμ§λ₯Ό 보λ΄κ³ μ νλ λμ Cκ° μ£Όμ΄μ§λ€.
(1 <= N <= 30,000, 1 <= M <= 200,000, 1 <= C <= N)
2. λμ§Έ μ€λΆν° M+1λ²μ§Έ μ€μ κ±Έμ³μ ν΅λ‘μ λν μ 보 X, Y, Zκ° μ£Όμ΄μ§λ€. μ΄λ νΉμ λμ Xμμ λ€λ₯Έ νΉμ λμ Yλ‘ μ΄μ΄μ§λ ν΅λ‘κ° μμΌλ©°, λ©μμ§κ° μ λ¬λλ μκ°μ΄ ZλΌλ μλ―Έλ€.
(1 <= X, Y <= N, 1 <= Z <= 1,000)
μΆλ ₯쑰건
첫째 μ€μ λμ Cμμ λ³΄λΈ λ©μμ§λ₯Ό λ°λ λμμ μ΄ κ°μμ μ΄ κ±Έλ¦¬λ μκ°μ 곡백μΌλ‘ ꡬλΆνμ¬ μΆλ ₯νλ€.
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
n, m, start = map(int, input().split())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
x, y, z = map(int, input().split())
graph[x].append((y, z))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if distance[now] < dist:
continue
for i in graph[now]:
cost = dist + i[1]
if cost < distance[i[0]]:
distance[i[0]] = cost
heapq.heappush(q, (cost, i[0]))
dijkstra(start)
count = -1
max_distance = 0
for d in distance:
if d != INF:
count += 1
max_distance = max(max_distance, d)
print(count, max_distance)
'π Problem Solving > μ΄μ·¨μ½' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[μ΄μ·¨μ½-κ·Έλν μ΄λ‘ ] κ°μ λ μλ‘μ μ§ν© μκ³ λ¦¬μ¦ μμ€μ½λ / Python (0) | 2021.07.01 |
---|---|
[μ΄μ·¨μ½-μ΅λ¨ κ²½λ‘] κ°μ λ λ€μ΅μ€νΈλΌ μκ³ λ¦¬μ¦ / Python (0) | 2021.05.19 |