문제 링크 http://icpc.me/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 풀이 플로이드 와샬을 이용하면 O(N^3)에 풀 수 있다. 플로이드 와샬을 돌린 후 dp[i][i]에 음수가 있는지 체크하면 된다. 코드 #include using namespace std; const int N = 502; const int INF = 1e8; int dp[N][N]; int main() { int tc; scanf("%d", &tc); while (tc--) { int n, m, w;..