코딩/BOJ & 알고스팟
[BOJ 2458] 키 순서
hoon222y
2017. 8. 27. 15:47
https://www.acmicpc.net/problem/2458
자신으로 올 수 있는 지점 + 자신이 갈 수 있는 지점 = n-1 일 경우 자신의 순위를 알 수 있다.
n의 범위가 500까지 이므로 플로이드 워셜을 사용하였다. 근데 O(N^3)인데 1초안에 어케 들어오는거지 ?;;;;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <stack> #include <deque> #include <queue> #include <cmath> #include <stdio.h> #define INF 1e9 typedef long long ll; using namespace std; int n,m,arr[555][555]; int main(){ scanf("%d%d" , &n,&m); memset(arr,0,sizeof(arr)); for(int i=1;i<=m;i++){ int a,b; scanf("%d%d" , &a,&b); arr[a][b] = 1; } for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(arr[i][k] == 1 && arr[k][j] == 1){ arr[i][j] = 1; } } } } int ans = 0; for(int i=1;i<=n;i++){ int sumv = 0; for (int j=1;j<=n;j++){ if(i!= j){ sumv += arr[i][j]; sumv += arr[j][i]; } } if(sumv == n-1){ ans++; } } cout <<ans <<endl; return 0; } | cs |