Search
Duplicate

경로 찾기

주차
18
문제번호
11403
언어
C++
티어
실버
유형
플로이드-와샬
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

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++
복사