knightL

Untitled

Oct 9th, 2011
709
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.80 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. #include <iostream>
  6. #include <sstream>
  7. #include <string.h>
  8. #include <algorithm>
  9. #include <queue>
  10. using namespace std;
  11.  
  12. vector<vector<int> > v;
  13. bool know[101][101];
  14. int dist[101][101];
  15.  
  16. struct msg
  17. {
  18.     int send;
  19.     int prevsend;
  20.     int len;
  21.     msg(int send=0,int prevsend=0,int len=0): send(send),prevsend(prevsend),len(len){}
  22. };
  23.  
  24. struct cmp
  25. {
  26.     bool operator()(msg a,msg b)
  27.     {
  28.         return a.len>b.len;
  29.     }
  30. };
  31.  
  32.  
  33. int main()
  34. {
  35.     map<string,int> dict;
  36.     vector<int> name;
  37.     vector<string> sname;
  38.     int dictcnt=0;
  39.     int n,t;
  40.     cin>>n;
  41.     v.resize(n);
  42.     string a,b;
  43.     for(int i=0;i<n;i++)
  44.     {
  45.         cin>>a>>t;
  46.         if(dict[a]==0)
  47.         {
  48.             dict[a]=++dictcnt;
  49.             name.push_back(a.size());
  50.             sname.push_back(a);
  51.         }
  52.         while(t--)
  53.         {
  54.             cin>>b;
  55.             if(dict[b]==0)
  56.             {
  57.                 dict[b]=++dictcnt;
  58.                 name.push_back(b.size());
  59.                 sname.push_back(b);
  60.             }
  61.             v[dict[a]-1].push_back(dict[b]-1);
  62.         }
  63.     }
  64.     getline(cin,a);
  65.     getline(cin,a);
  66.     memset(dist,-1,sizeof(dist));
  67.     dist[0][0]=a.length();
  68.     know[0][0]=1;
  69.     priority_queue<msg,vector<msg>,cmp > q;
  70.     for(int i=0;i<v[0].size();i++)
  71.     {
  72.         q.push(msg(v[0][i],0,dist[0][0]));
  73.     }
  74.     while(!q.empty())
  75.     {
  76.         msg c=q.top();
  77. //      cerr<<c.second<<" "<<c.first<<endl;
  78.         q.pop();
  79.         if(c.len>140) continue;
  80.         if(know[c.send][c.prevsend]) continue;
  81.         know[c.send][c.prevsend]=true;
  82.         dist[c.send][c.prevsend]=c.len;
  83.         for(int i=0;i<v[c.send].size();i++)
  84.         {
  85.             if(!know[v[c.send][i]][c.send])
  86.                 q.push(msg(v[c.send][i],c.send,c.len+4+name[c.prevsend]));
  87.         }
  88.     }
  89.     int res=0;
  90.     for(int i=0;i<n;i++)
  91.     {
  92.         for(int j=0;j<n;j++)
  93.             know[i][0]|=know[i][j];
  94.         if(know[i][0])
  95.             res++;
  96.     }
  97.     printf("%d\n",res);
  98.     for(int i=0;i<n;i++)
  99.     {
  100.         if(know[i][0])
  101.             cout<<sname[i]<<endl;
  102.     }
  103.     return 0;
  104. }
  105.  
  106.  
Advertisement
Add Comment
Please, Sign In to add comment