(C++) 백준 11404 플로이드

문제 및 풀이

https://www.acmicpc.net/problem/11404

제목처럼 플로이드 와샬 문제 ~
전체 노드의 최단 거리를 찾을때 효율적이다.

a 노드에서 b 노드로 갈때 또 다른 c 노드를 경유해서 가는 경우도 찾아 최소값으로 갱신한다. (a→b vs a→c→b)
전체 배열을 3중 for문으로 돌면서 (i-y 위치, j-x 위치, k-경유 노드) 계산하면 된다.

    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(arr[i][k]+arr[k][j]<arr[i][j])
                    arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }

코드

#include <iostream>
using namespace std;

const int INF =10000001;
int n,m;
int a,b,c;
int arr[105][105];


int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin>>n>>m;

    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) {
            if(i==j) continue;
            arr[i][j]=INF;
    }


    for(int i=0; i<m; i++){
        cin>>a>>b>>c;
        arr[a][b]= min(arr[a][b],c);
    }

    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(arr[i][k]+arr[k][j]<arr[i][j])
                    arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }

    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i==j || arr[i][j]>= INF) cout<<"0 ";
            else
            cout<<arr[i][j]<<" ";
        }
        cout<<'\n';
    }


}