Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <vector>
- #include <string>
- #include <map>
- #include <iostream>
- #include <sstream>
- #include <string.h>
- #include <algorithm>
- #include <queue>
- using namespace std;
- vector<vector<int> > v;
- bool know[101][101];
- int dist[101][101];
- struct msg
- {
- int send;
- int prevsend;
- int len;
- msg(int send=0,int prevsend=0,int len=0): send(send),prevsend(prevsend),len(len){}
- };
- struct cmp
- {
- bool operator()(msg a,msg b)
- {
- return a.len>b.len;
- }
- };
- int main()
- {
- map<string,int> dict;
- vector<int> name;
- vector<string> sname;
- int dictcnt=0;
- int n,t;
- cin>>n;
- v.resize(n);
- string a,b;
- for(int i=0;i<n;i++)
- {
- cin>>a>>t;
- if(dict[a]==0)
- {
- dict[a]=++dictcnt;
- name.push_back(a.size());
- sname.push_back(a);
- }
- while(t--)
- {
- cin>>b;
- if(dict[b]==0)
- {
- dict[b]=++dictcnt;
- name.push_back(b.size());
- sname.push_back(b);
- }
- v[dict[a]-1].push_back(dict[b]-1);
- }
- }
- getline(cin,a);
- getline(cin,a);
- memset(dist,-1,sizeof(dist));
- dist[0][0]=a.length();
- know[0][0]=1;
- priority_queue<msg,vector<msg>,cmp > q;
- for(int i=0;i<v[0].size();i++)
- {
- q.push(msg(v[0][i],0,dist[0][0]));
- }
- while(!q.empty())
- {
- msg c=q.top();
- // cerr<<c.second<<" "<<c.first<<endl;
- q.pop();
- if(c.len>140) continue;
- if(know[c.send][c.prevsend]) continue;
- know[c.send][c.prevsend]=true;
- dist[c.send][c.prevsend]=c.len;
- for(int i=0;i<v[c.send].size();i++)
- {
- if(!know[v[c.send][i]][c.send])
- q.push(msg(v[c.send][i],c.send,c.len+4+name[c.prevsend]));
- }
- }
- int res=0;
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- know[i][0]|=know[i][j];
- if(know[i][0])
- res++;
- }
- printf("%d\n",res);
- for(int i=0;i<n;i++)
- {
- if(know[i][0])
- cout<<sname[i]<<endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment