zju Alien Security spfa #include<iostream> #include<algorithm> #include<string> #include<cstring> #include<queue> using namespace std; const int INF=1000000; int vis[101],g[101][101],d[101]; int n,ET;//ET目标房间 void spfa()//Bellman_Ford的队列实现,求单源点最短路径 { queue<int > q; bool inq[101]; for(int i=0;i<n;i++)d[i]=(i==ET?0:INF); memset(inq,0,sizeof(inq)); q.push(ET); while(!q.empty()) { int t=q.front();q.pop(); inq[t]=false; for(int i=0;i<n;i++)//一般用邻接链表 { if(g[i][t]&&d[i]>d[t]+1) { d[i]=d[t]+1; if(!inq[i]) { inq[i]=1; q.push(i); } } } } } bool BFS(int x)//假设x去掉,是否能从起点到终点,即x是否为必经之点 { memset(vis,0,sizeof(vis)); queue <int> q; q.push(0); vis[0]=1; while(!q.empty()) { int t=q.front(); q.pop(); if(t==ET)return 0; for(int i=0;i<n;i++) { if(!vis[i]&&g[t][i]&&i!=x) { vis[i]=1; q.push(i); } } } return 1; } int main() { int cas; string s; cin>>cas; while(cas--) { memset(g,0,sizeof(g)); cin>>n>>ET;//此乃变态输入 getline(cin,s); for(;;) { if(getline(cin,s)==0||s=="")break; int a=s[0]-'0',b=s[2]-'0'; g[a][b]=1; } spfa(); int ans=INF,ANS=-1; for(int i=0;i<n;i++) { if(i!=ET&&BFS(i))//如果i为必经点 { if(d[i]<ans){ans=d[i];ANS=i;} } } if(ANS==-1)cout<<"Put guards in room 0."<<endl; else cout<<"Put guards in room "<<ANS<<"."<<endl; if(cas)cout<<endl; } }
zju1085Alien Security
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=85