Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<cstdio>
- #include<queue>
- #include<cmath>
- #include<ctime>
- #include<map>
- #include<iostream>
- #include<algorithm>
- #include<vector>
- #include<string>
- using namespace std;
- typedef unsigned long long u64;
- const int INF = 1000*1000*1000;
- map<string, int> mp;
- vector<string> pm;
- int _mp = 0;
- int get_id(string &s)
- {
- map<string, int>::iterator it = mp.find(s);
- if(it == mp.end())
- {
- mp[s] = _mp;
- pm[_mp] = s;
- _mp++;
- return _mp-1;
- }
- else
- return it->second;
- }
- string get_name(int id)
- {
- return pm[id];
- }
- class man
- {
- public:
- man(int i = 0, int p = 0, int s = 0): id(i), prevsend(p), send(s) {}
- int id;
- int prevsend;
- int send;
- };
- bool operator<(const man &a, const man &b)
- {
- return a.send < b.send;
- }
- int main()
- {
- int n;
- cin >> n;
- int m, id;
- string name;
- pm = vector<string> (n);
- vector<vector<int> > g(n);
- for(int i = 0; i < n; i++)
- {
- cin >> name >> m;
- id = get_id(name);
- for(int j = 0; j < m; j++)
- {
- cin >> name;
- g[id].push_back(get_id(name));
- }
- }
- string message;
- getline(cin, message);
- getline(cin, message);
- priority_queue<man> q;
- vector<int> d(n, INF);
- q.push(man(0, 0, message.size()));
- d[0] = 0;
- while(!q.empty())
- {
- man top = q.top(); q.pop();
- for(int i = 0; i < g[top.id].size(); i++)
- {
- if(d[g[top.id][i]] > top.send && top.send <= 140)
- {
- d[g[top.id][i]] = top.send;
- q.push(man(g[top.id][i], top.send, top.send+6+get_name(top.id).size()));
- }
- }
- }
- int res = 0;
- for(int i = 0; i < n; i++)
- if(d[i] != INF)
- res++;
- cout << res << endl;
- for(int i = 0; i < n; i++)
- if(d[i] != INF)
- cout << get_name(i) << endl;
- return 0;
- }
- /*
- 3
- a 1 b
- b 1 c
- c 0
- aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
- */
Add Comment
Please, Sign In to add comment