[실1] 11403 - 경로 찾기

플로이드 와샬

#include <iostream>
 
#define    INF     100000
#define NODE 1000
 
using namespace std;
 
int graph[NODE][NODE]{ 0 };
 
void Floyd_washall()
{
    int n; cin >> n;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cin >> graph[i][j];
    }
    for (int k = 0; k < n; k++) // 거쳐가는 노드
    {
        for (int i = 0; i < n; i++) // 출발지 노드
        {
            for (int j = 0; j < n; j++) // 도착지 노드
            {
                if (graph[i][k] && 
                    graph[k][j])
                    graph[i][j]= 1;
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
            cout << graph[i][j] << " ";
 
        cout << '\n';
    }
}
 
int main(void)
{
    Floyd_washall();
    return 0;
}