Source Code

Problem: 1130  User: yzhw 
Memory: 256K  Time: 16MS 
Language: C++  Result: Accepted 

Source Code 
# include <iostream>
# include <vector>
# include <queue>
# include <cstring>
using namespace std;
int n,target;
vector<int> graph[10];
int c[10],co=0;
bool used[10];
int path[100];
void dfs(int pos,int level)
{
     if(used[pos]) return;
     else if(pos==0)
     {
        co++;
        c[0]++;
        for(int i=1;i<level;i++)
          c[path[i]]++;
        return;
     }
     else
     {
         used[pos]=1;
         path[level]=pos;
         for(int i=0;i<graph[pos].size();i++)
           dfs(graph[pos][i],level+1);
         used[pos]=0;
         return;
     }
}
int bfs()
{
    memset(used,0,sizeof(used));
    queue<int> q;
    q.push(target);
    used[target]=1;
    while(!q.empty())
    {
        int pos=q.front();
        q.pop();
        if(c[pos]==co) return pos;
        for(int i=0;i<graph[pos].size();i++)
          if(!used[graph[pos][i]])
             {
                 used[graph[pos][i]]=1;
                 q.push(graph[pos][i]);
             }
    }
    return 0;
}
int main()
{
    cin>>n>>target;
    int t1,t2;
    memset(used,0,sizeof(used));
    while(cin>>t1>>t2)
    {
       graph[t2].push_back(t1);
    }
    dfs(target,0);
    cout<<"Put guards in room "<<bfs()<<"."<<endl;
   // system("pause");
    return 0;
}

• ？？？ (1289) xiaostone 2011-06-04 17:59:46