제출 #250141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250141		Kevin_Zhang_TW	Cop and Robber (BOI14_coprobber)	C++17	16 / 100	465 ms	3192 KiB

coprobber

#include "coprobber.h"
#include <bits/stdc++.h>
#define pb emplace_back

using namespace std;
#define MAX_N 500
const int inf = 1e9;

// modify the following functions
// you can define global variables and functions
int dp[MAX_N][MAX_N];
int now, n;
vector<int> edge[MAX_N];
bool con[MAX_N][MAX_N];
bool dfs(int tar, int now, int lst) {
	if (now == tar) return true;
	for (int u : edge[now]) if (u != lst && dfs(tar, u, now))
		return true;
	return false;
}
int start(int n, bool A[MAX_N][MAX_N]) {
	int m = 0;
	for (int i = 0;i < n;++i)
		for (int j = 0;j < n;++j) {
			dp[i][j] = A[i][j] ? 1 : inf, con[i][j] = A[i][j], dp[i][i] = 0, m += A[i][j];
			if (A[i][j])
				edge[i].pb(j);
		}
	
	assert(m == (n-1) * 2);
//	for (int i = 0;i < n;++i)
//		for (int j = 0;j < n;++j) if (i != j)
//			assert(A[i][j]);
	for (int a:{1,1,1})
	for (int k = 0;k < n;++k)
		for (int i = 0;i < n;++i)
			for (int j = 0;j < n;++j)
				dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

	return now = 0;
//	int res = 0;
//	for (int i = 0;i < n;++i)
//		if (dp[i][i] <= n)
//			res = max(res, dp[i][i]), cerr << dp[i][i] << '\n';
//	if (res > 4) return -1;
//
//	return 0;

}

 
int nextMove(int R) {
	if (now == R) 
		return R;
//	for (int i= 0 ;i < n;++i)
//		if (con[now][i]) {
//			dis = min(dis, dp[i][R]);
//			if (dis == dp[i][R])
//				go = i;
//		}
//	return now = go;
	for (int u : edge[now])
		if (dfs(R, u, now)) {
			assert(dp[u][R] == dp[now][R]-1);
            assert(con[u][now] && con[now][u]);
			return now = u;
		}
	return -1;
} 

컴파일 시 표준 에러 (stderr) 메시지

coprobber.cpp: In function 'int start(int, bool (*)[500])':
coprobber.cpp:34:11: warning: unused variable 'a' [-Wunused-variable]
  for (int a:{1,1,1})
           ^

• Subtask 1: 16 / 16
• Subtask 2: 0 / 14
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40