[대표 유형] 플로이드 워셜 알고리즘

문제 설명

정점의 개수 n, 단방향 간선 정보가 담긴 edges, 쿼리 정보가 담긴 query가 매개 변수로 주어질 때, query 별로 시작 정점에서 출발하여 도착 정점에 도착하기까지 경로의 길이를 반환하는 solution 함수를 작성하시오.

문제에서 주어지는 그래프는 모든 정점이 다른 정점으로 이동할 수 있으며, 음수 사이클이 존재하지 않는 그래프만 주어진다고 가정합니다.

개념 설명

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 주어진 그래프에 대해 임의의 두 정점 사이의 최단 경로를 구하는 알고리즘입니다.

플로이드 워셜 알고리즘은 간선의 가중치 중 음수가 포함되어 있어도 적용할 수 있는 알고리즘입니다. 이 때문에 음수 사이클이 존재하는 그래프의 경우에는 최단 거리가 음의 무한대로 발산하여 음수 사이클의 존재 여부를 파악하는데 적용되기도 합니다.

아래와 같은 단방향 간선 그래프가 주어졌다고 가정합니다.
이때 각 정점에서 출발하여 다른 정점으로 도착할 때 경로 길이를 D[i][j]로 정의합니다.

이후 D[i][j]를 중간에 다른 정점을 거쳐서 이동하는 경우를 고려하여 최단 경로 길이로 갱신합니다.
갱신 식은 $D[i][j] = min(D[i][j], D[i][k]+D[k][j])$ 입니다.
k=1인 경우부터 시작하면, 갱신 결과는 다음과 같습니다.

k=2인 경우의 갱신 결과는 다음과 같습니다.

k=3인 경우의 갱신 결과는 다음과 같습니다.

k=4인 경우의 갱신 결과는 다음과 같습니다.

갱신 식에서 주어진 k를 모든 정점에 대해서 갱신하면, i번 정점에서 j번 정점에 도착하는 최단 경로 길이가 D[i][j]로 갱신됩니다.
이때 임의의 정점에 대해서 D[i][i]가 하나라도 음수라면 음수 사이클이 존재하는 것이며, D[i][j]=INF인 경우가 있다면 i번 정점에서 j번 정점으로는 이동할 수 없음을 의미합니다.

제한 사항

• 정점의 개수 n은 2 이상 100 이하의 자연수입니다.
• 단방향 간선 정보 edges의 원소는 특정 간선의 시작 정점 x, 도착 정점 y, 간선의 길이 w로 이루어집니다.
  • x, y는 1 이상 n 이하의 자연수입니다.
  • w는 -500 이상 500 이하의 정수입니다.
• 쿼리 정보 query의 원소는 출발 정점 s, 도착 정점 e로 이루어집니다.
  • s, e는 1 이상 n 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 개념 설명 부분의 예시와 동일합니다.

2번 테스트케이스 설명

• 입력된 단방향 그래프에서 최단 경로 길이 배열 Dist[i][j] (= 출발 정점(i)에서 도착 정점(j) 까지 최단 경로의 길이) 는 다음과 같습니다.