Memo
로직 설명
•
플로이드-와샬을 적용시켰습니다.
•
모든 정점에서 모든 정점으로의 최단 거리를 구하는 알고리즘이지만, 그것이 의미하는 것은 결국 모든 정점에서 모든 정점으로 갈 수 있는지 이기 때문입니다.
Code
제출 날짜
@5/3/2021
메모리
2028 KB
시간
4 ms
#include <iostream>
#define endl "\n"
int N;
bool g_map[101][101];
inline void io_faster()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
}
inline void input()
{
io_faster();
std::cin >> N;
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < N ; j++)
std::cin >> g_map[i][j];
}
inline void make_floyd()
{
for (int k = 0 ; k < N ; k++)
for (int i = 0 ; i < N ; i++)
for (int j = 0 ; j < N ; j++)
if (g_map[i][k] && g_map[k][j])
g_map[i][j] = 1;
}
inline void solve()
{
make_floyd();
}
inline void print_val()
{
for (int i = 0 ; i < N ; i++)
{
for (int j = 0 ; j < N ; j++)
std::cout << g_map[i][j] << " ";
std::cout << endl;
}
}
int main()
{
input();
solve();
print_val();
return (0);
}
C++
복사