n개의 도시가 있고, 도시 사이를 연결하는 m개의 도로가 있다고 가정해 봅시다. 각 도로는 {출발지, 목적지, 가중치} 형식의 배열로 주어집니다. 여기서 s, t, k가 모두 도시를 나타내는 트리플릿(triplet) (s, t, k)를 정의합니다.
우리가 해야 할 일은 도시 s에서 도시 t로 이동할 때 걸리는 최소 시간을 구하는 것입니다. 단, s에서 t로 이동하는 과정에서는 번호가 1부터 k 사이에 있는 도시만 경유할 수 있습니다. 만약 s에서 도시 t에 도달할 수 없다면 해당 경우는 0으로 처리합니다. 이렇게 모든 트리플릿 (s, t, k)에 대해 최소 시간을 계산한 뒤, 그 값들을 모두 더한 합계를 출력하면 됩니다.
예를 들어 입력이 n = 4, m = 2, edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}과 같다면 출력은 63이 됩니다.
문제 해결 접근 방법
이 문제는 플로이드-워셜(Floyd–Warshall) 알고리즘의 변형으로 해결할 수 있습니다. 중간에 거칠 수 있는 정점의 범위를 하나씩 넓혀 가면서, 매 단계마다 현재까지 계산된 모든 최단 경로의 합을 누적하는 방식입니다. 해결 과정은 다음과 같습니다.
무한대(INF) 값으로 초기화된 2차원 배열 dvec을 정의한다
i := 0부터 i < n까지 반복하며:
dvec[i, i] := 0
i := 0부터 i < m까지 반복하며:
a := edges[i]의 첫 번째 값
b := edges[i]의 두 번째 값
c := edges[i]의 세 번째 값
a와 b에서 1을 빼 0 기반 인덱스로 변환
dvec[a, b] := c
res := 0
k := 0부터 k < n까지 반복하며:
i := 0부터 i < n까지 반복하며:
j := 0부터 j < n까지 반복하며:
dvec[i, j] := min(dvec[i, j], dvec[i, k] + dvec[k, j])
만약 dvec[i, j]가 무한대가 아니라면:
res := res + dvec[i, j]
res를 출력한다C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 봅시다.
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
void solve(int n, int m, vector<tuple<int, int, int>> edges){
vector<vector<int>> dvec(n, vector<int>(n, INF));
for(int i = 0; i < n; i++)
dvec[i][i] = 0;
for(int i = 0; i < m; i++) {
int a = get<0> (edges[i]);
int b = get<1> (edges[i]);
int c = get<2> (edges[i]);
a--; b--;
dvec[a][b] = c;
}
int res = 0;
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
dvec[i][j] = min(dvec[i][j], dvec[i][k]+dvec[k][j]);
if(dvec[i][j] != INF)
res += dvec[i][j];
}
}
}
cout << res << endl;
}
int main() {
int n = 4, m = 2;
vector<tuple<int, int, int>> edges = {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}};
solve(n, m, edges);
return 0;
}입력
4, 2, {{1, 2, 5}, {2, 3, 4}, {3, 4, 3}}출력
63