BOJ 11403 - 경로 찾기

www.acmicpc.net/problem/11403

11403번: 경로 찾기

플로이드 와샬 알고리즘 그대로 쓰되,

i 번째에서 j 번째 노드로 이동 가능하면 1로

그렇지 않으면 0으로 출력해주면 된다.

최단거리를 출력하는게 아니라 그냥 이동 가능한지 아닌지만 보는 문제.

 

- c++

 

#include <algorithm>
#include <iostream>
 
#define MAX 100
#define INF 1e9
 
using namespace std;
 
int n;
int dist[MAX][MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> dist[i][j];
            if (!dist[i][j]) dist[i][j] = INF;
        }
    }
    
    for (int k = 0; k < n; ++k) 
        for (int i = 0; i < n; ++i) 
            for (int j = 0; j < n; ++j) 
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] == INF) cout << 0 << " ";
            else cout << 1 << " "; 
        }
        cout << "\n";
    }
    
    return 0;
}