백준 11404 플로이드 - C++

11404번: 플로이드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m, from, to, cost;
int bus[101][101];

// 플로이드-와샬 알고리즘
// 1~2로 가는데 만약 3을 거쳐가는게 더 빠르다고 하면 3을 거쳐가는 비용으로 업데이트
void F(){
    for(int v = 1; v <= n; v++){
        for(int f = 1; f <= n; f++){
            if(!bus[f][v])
                continue;
            for(int t = 1; t <= n; t++){
                if(!bus[v][t] || f == t)
                    continue;
                
                if(bus[f][t] > bus[f][v] + bus[v][t] || !bus[f][t])
                    bus[f][t] = bus[f][v] + bus[v][t];
            }
        }
    }
}

int main(){
    scanf("%d", &n);
    scanf("%d", &m);
    for(int i = 0; i < m; i++){
        scanf("%d %d %d", &from, &to, &cost);

        if(!bus[from][to])
            bus[from][to] = cost;
        else
            bus[from][to] = min(bus[from][to], cost);
    }

    F();

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            printf("%d ", bus[i][j]);
        }
        printf("\n");
    }
}

---

 플로이드-와샬의 간단한 이론만 알 수 있다면 풀 수 있는 문제입니다. '출발-도착' 보다 '출발-경유지-도착'이 더 빠른경우 찾아낼 수 있는 알고리즘으로 시간복잡도가 n^3이다 보니 n이 크지 않은 문제들, 모든 출발지-도착지 쌍을 구하는 경우에 사용되게 됩니다.

  풀이를 하면서 조금 헷갈린 부분은

void F(){
    for(int v = 1; v <= n; v++){
        for(int f = 1; f <= n; f++){
            if(!bus[f][v])
                continue;
            for(int t = 1; t <= n; t++){
                if(!bus[v][t] || f == t)
                    continue;
                
                if(bus[f][t] > bus[f][v] + bus[v][t] || !bus[f][t])
                    bus[f][t] = bus[f][v] + bus[v][t];
            }
        }
    }
}

 위 플로이드 함수에서 제일 안쪽 포문의 두번째 if에 있는 !bus[f][t] 였습니다. 처음에는 위에 넣어야 하는게 아닌가 했지만 생각해보니 아래 if에 둬야 출발지-도착지를 전부 구할 수 있게 됩니다.