제출 #250115

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

coprobber

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

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;
bool con[MAX_N][MAX_N];
int start(int n, bool A[MAX_N][MAX_N]) {

	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];
//	for (int i = 0;i < n;++i)
//		for (int j = 0;j < n;++j) if (i != j)
//			assert(A[i][j]);
	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 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 (con[now][R] || now == R)
		return now = R;
	int go = now, dis = INT_MAX;
	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;
} 

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