18243 Small World Network
문제 링크
https://www.acmicpc.net/problem/18243
풀이
전형적인 플로이드-와샬 문제였당
친구 관계가 있는 경우 cost를 1, 없으면 큰 값을 주고 플로이드-와샬을 통해 모든 정점으로부터 모든 정점까지의 거리의 최소값을 구한다. 만약 정점과 정점 사이의 거리가 6 이상이 되는 경우가 있다면 Big World!를 출력하고 그렇지 않다면 Small World!를 출력한다.
C++ 코드
#include <iostream>
#include <algorithm>
using namespace std;
int N, K;
int INF = 10000;
int arr[101][101];
void floydWarshall(){
int d[101][101];
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(arr[i][j] == 0){d[i][j] = INF; continue;}
d[i][j] = arr[i][j];
}
}
for(int k=1; k<=N; k++){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(d[i][k] + d[k][j] < d[i][j]){
d[i][j] = d[i][k] + d[k][j];
}
}
}
}
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
if(d[i][j] > 6 || d[i][j] == INF){
cout<<"Big World!"<<endl;
return;
}
}
}
cout<<"Small World!"<<endl;
return;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin>>N>>K;
for(int i=0; i<K; i++){
int A, B;
cin>>A>>B;
arr[A][B] = arr[B][A] = 1;
}
floydWarshall();
return 0;
}
Author And Source
이 문제에 관하여(18243 Small World Network), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@binary_j/18243-Small-World-Network저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)