bfs，数据范围是10
View Code #include#include #include #include #include using namespace std;#define maxn 10int n, et;bool map[maxn][maxn];bool vis[maxn];int dist[maxn];int dist1[maxn];void input(){ memset(map, 0, sizeof(map)); scanf("%d%d", &n, &et); int a, b; while (~scanf("%d%d", &a, &b)) map[b][a] = true;}void bfs(int s, int guard_room, int* dist){ queue q; memset(vis, 0, sizeof(vis)); memset(dist, -1, sizeof(int) * n); vis[s] = true; q.push(s); dist[s] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < n; i++) if (map[u][i] && !vis[i] && i != guard_room) { q.push(i); vis[i] = true; dist[i] = dist[u] + 1; } }}int work(){ int ret = 0; for (int i = 1; i < n; i++) if (i != et) { bfs(et, i, dist1); if (dist1[0] != -1) continue; if (dist[ret] > dist[i]) ret = i; } return ret;}int main(){ //freopen("t.txt", "r", stdin); input(); bfs(et, -1, dist); printf("Put guards in room %d.\n", work()); return 0;}