본문 바로가기

알고리즘

부족 연합에 보내는 편지

New Era · 4번Lv. 3최단 경로

부족 연합에 보내는 편지

문제 설명

라이언 타운으로 가기 전에 라이캣은 여러 부족에게 편지를 보내 함께 일어서자고 부탁하기로 했습니다. 개굴 마을, JAVA 마을, 당근 마을처럼 부족마다 쓰는 말이 달라서 편지를 번역해야 합니다.

"고양이어로 쓴 편지가 모든 부족에게 제대로 닿아야 한다냥."

"번역기를 여러 번 거치면 뜻이 조금씩 틀어진다 개굴. 손실이 가장 적은 길로 보내야 한다 개굴!"

대리인 No.1이 만든 번역기들이 있습니다. 번역기 하나는 한 언어에서 다른 한 언어로, 한 방향으로만 번역하고, 번역기마다 '정확도 손실'이 정해져 있습니다. 편지가 번역기를 여러 번 거치면 손실은 모두 더해집니다.

언어는 0번부터 n-1번까지 있고, 0번이 라이캣이 쓰는 고양이어입니다. 언어 수 n과 번역기 목록 translators가 주어질 때, 고양이어 편지를 각 언어로 옮길 때 생기는 손실 합의 최솟값을 0번 언어부터 차례로 리스트에 담아 반환하세요.

  • 0번 언어(고양이어)의 값은 0입니다.
  • 어떤 번역기를 어떻게 거쳐도 옮길 수 없는 언어는 -1입니다.

제한 사항

  • 입력은 [n, translators] 형태입니다.
  • 1 ≤ n ≤ 10,000
  • 0 ≤ translators의 길이 ≤ 50,000
  • 원소 [a, b, loss]는 a번 언어를 b번 언어로 옮기는 번역기이고, 정확도 손실이 loss라는 뜻입니다. 거꾸로(b → a)는 옮기지 못합니다.
  • 0 ≤ a, b ≤ n - 1, a ≠ b, 0 ≤ loss ≤ 100 (모두 정수)
  • 같은 두 언어 사이에 번역기가 여러 개 있을 수 있습니다.

입출력 예

입력출력
[4, [[0, 1, 5], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 7]]][0, 3, 1, 4]
[3, [[1, 0, 2], [0, 1, 4]]][0, 4, -1]
[5, [[0, 1, 0], [1, 2, 0], [2, 3, 10], [0, 3, 9], [3, 4, 1], [4, 3, 0]]][0, 0, 0, 9, 10]

입출력 설명

첫 번째 예

0번은 고양이어, 1번은 개굴어, 2번은 JAVA어, 3번은 당근어라고 해 봅시다.

  • 개굴어(1번): 바로 옮기면 손실 5, JAVA어를 거치면 1 + 2 = 3이므로 3입니다.
  • JAVA어(2번): 바로 옮기면 손실 1입니다.
  • 당근어(3번): 고양이어 → JAVA어 → 개굴어 → 당근어로 옮기면 1 + 2 + 1 = 4입니다. JAVA어에서 바로 옮기면 1 + 7 = 8이라 더 큽니다.

두 번째 예

1번 → 0번 번역기는 0번 → 1번으로 쓸 수 없습니다. 1번 언어는 0번 → 1번 번역기로 옮겨 4입니다. 2번 언어로 옮기는 번역기는 없으므로 -1입니다.

세 번째 예

손실이 0인 번역기도 있습니다. 3번 언어는 2번을 거치면 10, 바로 옮기면 9이므로 9이고, 4번 언어는 3번을 거쳐 9 + 1 = 10입니다.

예시 테스트

#입력기대값
1[4, [[0, 1, 5], [0, 2, 1], [2, 1, 2], [1, 3, 1], [2, 3, 7]]][0, 3, 1, 4]
2[3, [[1, 0, 2], [0, 1, 4]]][0, 4, -1]
3[5, [[0, 1, 0], [1, 2, 0], [2, 3, 10], [0, 3, 9], [3, 4, 1], [4, 3, 0]]][0, 0, 0, 9, 10]

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.