1116.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1116 on 2005-12-27 at 23:42:27 */ 
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX = 16;
const int INF = 20000000;
const int src = 0;

bool map[MAX][MAX];
bool key[MAX], visit[MAX];
int path[MAX], dst[MAX];
int dis, n;

void DFS(int, int);

int main()
{
	int t, T, i;
	char line[MAX];

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		if(t != 0) putchar('\n');
		scanf("%d %d\n", &n, &dis);
		memset(map, false, sizeof(map));
		while(gets(line) != NULL && line[0] != 0) {
			int a, b;
			sscanf(line, "%d %d", &a, &b);
			map[a][b] = true;
		}
		for(i = 0; i < n; i++) key[i] = true, dst[i] = INF;
		DFS(src, 0);
		int best = 0;
		for(i = 0; i < n; i++) {
			if(key[i] && i != dis && dst[i] < dst[best]) best = i;
		}
		printf("Put guards in room %d.\n", best);
	}
	
	return 0;
}

void DFS(int p, int d)
{
	int i;
	if(p == dis) {
		for(i = 0; i < d; i++) dst[path[i]] = min(dst[path[i]], d-i);
		for(i = 0; i < n; i++) {
			if(!visit[i]) key[i] = false;
		}
	} else {
		path[d] = p; visit[p] = true;
		for(i = 0; i < n; i++) {
			if(map[p][i] && !visit[i]) DFS(i, d+1);
		}
		visit[p] = false;
	}
}