Alien Security hoj poj 最短路应用好题
/*题意是求一个离终点最近的点使得去掉该点之后起点到终点不连通。*//*对于距离最近，可以终点为源点作spfa，预处理出从终点到其余各点的最短路径，这里有些细节要注意，一个是松弛时应用map[i][x]的松弛的条件，而非map[x][i]，因为题意是有向图且路径方向是从起点到终点，然后直接相邻的两个点边权处理为1.最后是用深搜判断两点是否连通。*/#include <stdio.h>#include <cstring>#include <queue>using namespace std;int map[110][110];bool vis[110];int dist[110];int n,t;void spfa(int t){ memset(dist,0x7f,sizeof(dist)); dist[t]=0; queue <int> q; q.push(t); while(!q.empty()) { int u=q.front(); q.pop(); for(int i=0; i<n; i++) { if(map[i][u]&&dist[i]>dist[u]+1) q.push(i),dist[i]=dist[u]+1; } }}bool find(int x){ vis[x]=true; if(x==t) return true; for(int i=0; i<n; i++) { if(map[x][i]&&!vis[i]) if(find(i)) return true; } return false;}int main(){ int test; int ca=0; scanf("%d",&test); while(test--) { if(ca>0) printf("\n"); ca=1; scanf("%d%d",&n,&t); getchar(); char op[10]; memset(map,0,sizeof(map)); while(gets(op)) { if(strcmp(op,"")==0) break; int a,b; sscanf(op,"%d %d",&a,&b); map[a][b]=1; } spfa(t); int d=dist[0]; int pos=0; for(int i=1; i<n; i++) { if(t==i) continue; memset(vis,false,sizeof(vis)); vis[i]=true; if(!find(0)&&dist[i]<d) pos=i,d=dist[i]; } printf("Put guards in room %d.\n",pos); } return 0;}