warriorscats

Untitled

May 12th, 2021
560
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2. #include <iostream>
  3. #include <queue>
  4. #include <string>
  5. #include <map>
  6. #include <sstream>
  7. #include <vector>
  8. #include <set>
  9. #include <bitset>
  10. #include <limits>
  11. #define C 1001
  12.  
  13. using namespace std;
  14. using smart = pair<pair<int, int>, pair<bitset<C>, string>>; // (nr of colours, nr of nodes, mask of nodes, node)
  15. namespace std {
  16.     template<> struct greater<smart>: binary_function<smart, smart, bool> {
  17.         bool operator()(const smart& t1, const smart& t2) {
  18.             if (t1.second.first.count() != t2.second.first.count())
  19.                 return t1.second.first.count() < t2.second.first.count();
  20.             else return t1.first.second < t2.first.second;
  21.         }
  22.     };
  23.     bool operator<(const bitset<C>& a, const bitset<C>& b) {
  24.         return a.count() < b.count();
  25.     }
  26. };
  27. constexpr auto Inf = numeric_limits<int>::max();
  28.  
  29. ifstream fin("commando.in");
  30. ofstream fout("commando.out");
  31.  
  32. int n;
  33. string country, color, source, destination, text;
  34. map<string, vector<string>> Graph;
  35. map<string, string> CForC, Parent; // country => color
  36. set<string> Colors, Countries;
  37. map<string, int> ColVal;
  38.  
  39. priority_queue<smart, vector<smart>, greater<>> PQ;
  40. map<string, pair<pair<int, int>, bitset<C>>> Dist;
  41.  
  42. void Dijkstra(const string& src) {
  43.     bitset<C> mask; mask[ColVal[CForC[src]]] = true;
  44.     Dist[src] = make_pair(make_pair(1, 1), mask);
  45.     Parent[src] = "";
  46.     PQ.push(make_pair(make_pair(Dist[src].first.first, 1), make_pair(Dist[src].second, src)));
  47.  
  48.     while (!PQ.empty()) {
  49.         int curr_dist = PQ.top().first.first, curr_len = PQ.top().first.second;
  50.         bitset<C> curr_mask = PQ.top().second.first;
  51.         string curr_node = PQ.top().second.second;
  52.         PQ.pop();
  53.         if (curr_dist != Dist[curr_node].first.first) continue;
  54.  
  55.         for (const auto& neigh: Graph[curr_node]) {
  56.             bitset<C> new_mask = curr_mask; new_mask[ColVal[CForC[neigh]]] = true;
  57.             if (new_mask.count() < Dist[neigh].second.count()) {
  58.                 Dist[neigh] = make_pair(make_pair(new_mask.count(), curr_len + 1), new_mask);
  59.                 PQ.push(make_pair(make_pair(Dist[neigh].first.first, curr_len + 1), make_pair(new_mask, neigh)));
  60.                 Parent[neigh] = curr_node;
  61.             } else if (new_mask.count() == Dist[neigh].second.count() && curr_len + 1 < Dist[neigh].first.second) {
  62.                 Dist[neigh].first.second = curr_len + 1;
  63.                 PQ.push(make_pair(make_pair(Dist[neigh].first.first, curr_len + 1), make_pair(new_mask, neigh)));
  64.                 Parent[neigh] = curr_node;
  65.             }
  66.         }
  67.     }
  68. }
  69.  
  70. void print_chain(const string& curr) {
  71.     if (!Parent[curr].empty())
  72.         print_chain(Parent[curr]);
  73.     fout << curr << "\n";
  74. }
  75.  
  76. int main() {
  77.     fin >> n; fin.get();
  78.  
  79.     for (int i = 1; i <= n; ++i) {
  80.         getline(fin, text);
  81.         istringstream buffer(text); buffer >> country >> color;
  82.  
  83.         CForC[country] = color;
  84.         Colors.insert(color);
  85.         Countries.insert(country);
  86.  
  87.         // cout << country << " " << color << "\n";
  88.  
  89.         // istringstream buffer(neighs);
  90.         for (string word; buffer >> word;)
  91.             Graph[country].emplace_back(word);
  92.     }
  93.     fin >> source >> destination;
  94.  
  95.     int i = 0;
  96.     for (const auto& col: Colors)
  97.         ColVal[col] = i++;
  98.     for (const auto& ctr: Countries) {
  99.         bitset<C> mask; mask.set();
  100.         Dist[ctr] = make_pair(make_pair(Inf, Inf), mask);
  101.         // cout << ctr << " " << ColVal[CForC[ctr]] << " " << mask << "\n";
  102.     }
  103.  
  104.     Dijkstra(source);
  105.     if (Dist[destination].first.first != Inf) {
  106.         fout << Dist[destination].first.first << "\n";
  107.         print_chain(destination);
  108.     }
  109.     else fout << "No solution!";
  110.  
  111.     fin.close(), fout.close();
  112.     return 0;
  113. }
RAW Paste Data