leeingyun96   2년 전

3
2 1 4 2 1
0
1 1 2
2
0 1
1 0

위와 같은 7612번 SSSP 문제의 예제 입력에서 각 줄의 정수의 개수는 1, 5, 1, 3, 1, 2, 2이기 때문에 15입니다.

 

이러한 숫자가 T와 같거나 작을 수 있도록 입력을 넣으시면 됩니다. 꼭 맞출 필요는 없습니다.

 

각각의 데이터 만들기 문제에 적혀있는 T의 조건은 물론이고 7612번에 적혀있는 공통적인 조건도 적용됩니다.

 

파이썬 버전의 레퍼런스 코드는 아래와 같습니다. 다익스트라는 기본적인 이진 힙(1순위가 거리의 오름차순, 2순위가 정점의 인덱스의 오름차순)을 사용한 중복 정점을 허용하는 구현이고, 플로이드워셜은 기본적인 구현이고, 벨만포드는 약간의 최적화가 들어간 구현입니다.

댓글을 작성하려면 로그인해야 합니다.