π λ¬Έμ νμνκΈ°
- μ§νμ΄μ μ±νμ μ½μ μ₯μλ₯Ό μλ 쑰건μ λ§μ‘±νλλ‘ μ ν΄μΌ ν¨.
- μ§νμ΄, μ±νμ μΆλ° μμΉλ μ½μ μ₯μκ° λ μ μμ
- μ§νμ΄κ° 걸리λ μ΅λ¨ μκ°κ³Ό μ±νκ° κ±Έλ¦¬λ μ΅λ¨ μκ°μ ν©μ΄ μ΅μκ° λμ΄μΌ ν¨
- μ§νμ΄κ° μ±νλ³΄λ€ λ¦κ² λμ°©νλ κ³³μ μ½μ μ₯μκ° λ μ μμ
- 쑰건μ λ§μ‘±νλ μ₯μκ° μ¬λ¬ κ³³μ΄λΌλ©΄, μ§νμ΄λ‘λΆν° κ°μ₯ κ°κΉμ΄ κ³³ > λ²νΈκ° κ°μ₯ μμ μ₯μ μμΌλ‘ μ΅μ’ μ₯μλ₯Ό κ²°μ .
- 쑰건μ λ§μ‘±νλ μ₯μκ° μλ€λ©΄ -1
- 2 ≤ μ½μ μ₯μ ν보μ μ ≤ 100, 1 ≤ μ½μ μ₯μλ₯Ό μ°κ²°νλ μ΄ κΈΈμ μ ≤ M
- 1 ≤ κΈΈμ μμ, λ ≤ V, κΈΈμ μ§λκ°λ λ° κ±Έλ¦¬λ μκ°μ 10,000 μ΄νμ μμ°μμ΄λ©° κΈΈμ μλ°©ν₯μ
- 1 ≤ μ§νμ΄μ μμΉ, μ±νμ μμΉ ≤ J
ν΄λΉ λ¬Έμ λ κ° μ₯μλ₯Ό μ μ μΌλ‘ νκ³ , μ₯μλ€μ μ°κ²°νλ κΈΈμ κ°μ , κΈΈμ μ§λκ°λ λ° κ±Έλ¦¬λ μκ°μ κ°μ€μΉλ‘ μκ°νλ©΄, κ°μ€μΉκ° μλ μλ°©ν₯ κ·Έλνλ‘ ννν μ μλ€. λν μ§νμ΄μ μΆλ° μμΉ, μ±νμ μΆλ° μμΉμμ λ€λ₯Έ μ₯μκΉμ§μ μ΅λ¨ 거리μ ꡬν΄μΌνλ―λ‘ λ€μ΅μ€νΈλΌ μκ³ λ¦¬μ¦μ μ¬μ©ν μ μλ€.
μ±νλ₯Ό κΈ°μ€μΌλ‘ μ§νμ΄μ μΆλ° μ₯μκ° μλλ©΄μ κ°μ₯ κ°κΉμ΄ μμΉ μμΌλ‘ μ λ ¬νκ³ , μ§νμ΄λ₯Ό κΈ°μ€μΌλ‘ κ°κΉμ΄ μμΌλ‘ μ λ ¬νμ¬, μ±ν κΈ°μ€ κ°κΉμ΄ μ₯μλ₯Ό μ ννκ³ , μ§νμ΄ κΈ°μ€ κ·Έ μ₯μκ° μ±νλ³΄λ€ λ λ¨Όμ§ νμΈνλ©΄μ μ λ΅μ ꡬνλ€.
π μ½λ μ€κ³νκΈ°
- λ€μ΅μ€νΈλΌ ν¨μ dijkstra(start, graph)λ₯Ό μ μνλ€.
- μ°μ μμν hqλ₯Ό μμ±νκ³ (start, 0)μ μ½μ νλ€.
- μ΅λ¨ 거리λ₯Ό μ μ₯ν 리μ€νΈ distancesλ₯Ό μμ±νκ³ λͺ¨λ μμλ₯Ό 무νλλ‘ μ΄κΈ°νν ν, distances[start]μ 0μ μ μ₯νλ€.
- hqκ° λΉμ΄μμ λκΉμ§ μλ κ³Όμ μ λ°λ³΅νλ€.
- hqμμ μμλ₯Ό heappopνμ¬ κ°κ° cur_node, cur_costμ μ μ₯νκ³ , νμ¬ λ Έλκ° μ΄λ―Έ μ²λ¦¬λ λ ΈλλΌλ©΄ λ€λ₯Έ λ Έλμ νμμ κ³μνλ€.
- νμ¬ κΊΌλ΄μ§ λ Έλμ μ΄μν λ Έλλ₯Ό νμνλ©°, νμ¬ λ Έλλ₯Ό κ±°μ³κ° λμ μλλμ λΉμ©μ λΉκ΅ν΄ distancesλ₯Ό κ°±μ νκ³ , κ°±μ λμμΌλ©΄ μ΄μ λ Έλλ₯Ό hqμ heappushνλ€.
- λͺ¨λ νμμ΄ μ’ λ£λλ©΄ distancesλ₯Ό λ°ννλ€.
- μ½μ μ₯μ ν보μ μ V, μ½μ μ₯μλ₯Ό μ°κ²°νλ κΈΈμ μ Mμ μ λ ₯λ°λλ€.
- μ₯μλ€μ μ 보λ₯Ό μ μ₯ν κ·Έλν placesλ₯Ό μμ±νκ³ , Mκ°μ κΈΈ μ 보λ₯Ό μ λ ₯λ°μ μ μ₯νλ€.
- μ§νμ΄μ μμΉ Jμ μ±νμ μμΉ Sλ₯Ό μ λ ₯λ°λλ€.
- j_distancesμ dijkstra(J, places)μ λ°νκ°μ μ μ₯νκ³ , s_distancesμ dijkstra(S, places)μ λ°νκ°μ μ μ₯νλ€.
- total_distances 리μ€νΈλ₯Ό μμ±νκ³ , j_distancesμ s_distancesμμ κ°μ μμΉμ μμλΌλ¦¬ λν΄ κ·Έ κ²°κ³Όλ₯Ό (ν©ν 거리, μ§νμ΄ κΈ°μ€ κ±°λ¦¬, μμΉ λ²νΈ) ννλ‘ λ¦¬μ€νΈμ μ μ₯ν ν, (ν©ν 거리. μ§νμ΄ κΈ°μ€ κ±°λ¦¬, μμΉ) κΈ°μ€ μμΌλ‘ λ΄λ¦Όμ°¨μ μ λ ¬νλ€. μ΄λ, μμΉκ° J νΉμ Sμ΄κ±°λ, μ§νμ΄κ° κ° μ μλ μμΉ νΉμ μ±νκ° κ° μ μλ μμΉλ μ μΈνλ€.
- total_distancesλ₯Ό μμ°¨μ μΌλ‘ λλ©΄μ 쑰건과 μΌμΉνλ μμΉκ° μλμ§ μ°Ύλλ€.
- j_distances[ν΄λΉ μμΉ]κ° s_distances[ν΄λΉ μμΉ]μ κ°κ±°λ μλ€λ©΄ νμμ μ’ λ£νκ³ κ·Έ μμΉλ₯Ό μ΅μ’ μ½μ μ₯μλ‘ μΆλ ₯νλ€.
- νμ λμ€μ μ΄λ―Έ κ°μ΄ μ΅λ¨κ±°λ¦¬μ ν©μ μ΅μ(total_distances[0][0])μ λμ΄κ°λ©΄ νμμ μ’ λ£νκ³ -1μ μΆλ ₯νλ€.
- λͺ¨λ μμλ₯Ό νμνλλ° μ‘°κ±΄μ λ§μ‘±νλ μμΉλ₯Ό μ°Ύμ§ λͺ»νλ€λ©΄ -1μ μΆλ ₯νλ€.
πμλ νμ°¨ μμ μ¬ν
1νμ°¨
λ¬Έμ μ μ ν μ¬λ¬ κ°μ§ 쑰건λ€μ κΌΌκΌΌν μμ°¨μ μΌλ‘ μ²λ¦¬ν΄μΌ νλλ°, λ΄κ° μμ±ν μ½λλ 쑰건 μ€ μΌλΆλ₯Ό λμΉκ±°λ, μμλ₯Ό λ°κΏμ μ²λ¦¬ν΄μ μΌλΆ λ°λ‘μμ μλͺ»λ λ΅μ΄ λμλ€.
j_distances = dijkstra(J, places)
s_distances = dijkstra(S, places)
total_distances = [(j_distances[i] + s_distances[i], i) for i in range(V+1)]
total_distances.sort(key=lambda x:(x[0], x[1]))
for _, i in total_distances:
if i == J or i == S:
continue
if i != 0 and j_distances[i] <= s_distances[i]:
print(i)
break
else:
print(-1)
5 3
1 2 1
2 3 1
4 5 1
1 4
κΈ°λκ°
-1
μΆλ ₯κ°
2
2νμ°¨
쑰건μ μ²λ¦¬νλ λ‘μ§μ μμ νλλ°λ κ³μ μ€λ΅μ λ°κΈΈλ ν΄λΉ λ‘μ§μ μ¬μ ν λκ° μλͺ»λ λΆλΆμ΄ μλ€κ³ μκ°ν΄μ ν΄λΉ λΆλΆμ μμ νλλ°, κ·Έκ² μλλΌ λ€μ΅μ€νΈλΌ ν¨μ μ½λμ μ€λ₯κ° μμλ€. λ€μ΅μ€νΈλΌ ν¨μκ° μ μμ μΌλ‘ λμκ°λλ‘ μ½λλ₯Ό μμ ν΄μ£Όλ μ λ΅μ λ°μ μ μμλ€.
π μ λ΅ μ½λ
import sys
from heapq import heappush, heappop
input = sys.stdin.readline
INF = float('INF')
def dijkstra(start, graph):
hq = [(0, start)]
distances = [INF]*(V+1)
distances[start] = 0
while hq:
cur_cost, cur_node = heappop(hq)
if cur_cost > distances[cur_node]:
continue
for next_node, next_cost in graph[cur_node]:
new_cost = cur_cost + next_cost
if new_cost < distances[next_node]:
distances[next_node] = new_cost
heappush(hq, (new_cost, next_node))
return distances
V, M = map(int, input().split())
places = [[] for _ in range(V+1)]
for _ in range(M):
a, b, c = map(int, input().split())
places[a].append((b, c))
places[b].append((a, c))
J, S = map(int, input().split())
j_distances = dijkstra(J, places)
s_distances = dijkstra(S, places)
total_distances = [(j_distances[i] + s_distances[i], j_distances[i], i) for i in range(V+1) if i != J and i != S and j_distances[i] != float('INF') and s_distances[i] != float('INF')]
total_distances.sort(key=lambda x:(x[0], x[1], x[2]))
answer = -1
min_distance = total_distances[0][0] if total_distances else None
for distance, _, point in total_distances:
if distance > min_distance:
break
if j_distances[point] <= s_distances[point]:
answer = point
break
print(answer)