[11403] 경로 찾기

• 입력: 정점의 개수 N, N X N 인접행렬
• 출력: transitive closure 인접행렬
• 알고리즘: Floyd-Warshall
• 소스코드
#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std; int main() { int n, u; scanf("%d", &n); vector<vector<int> > adj(n, vector<int>(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &adj[i][j]); } } for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { if (i == k) continue; for (int j = 0; j < n; j++) { adj[i][j] = adj[i][j] | (adj[i][k] & adj[k][j]); } } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%d ", adj[i][j]); } printf("\n"); } return 0; }
• 문제 참고: https://www.acmicpc.net/problem/11403
• 알고리즘 참고 Floyd-Warshall