#include #include #include #include #include #include #include using namespace std; int parseID(string s) { return (s[0] - 'A') * ('Z' - 'A' + 1) + (s[1] - 'A'); } // Fucking hell. struct hash_pair { template size_t operator()(const pair& p) const { auto h1 = hash{}(p.first); auto h2 = hash{}(p.second); return h1 ^ (h2 << 1); } }; struct Graph { unordered_multimap conns; unordered_map rates; unordered_map, int, hash_pair> dist; }; void findLengths(Graph &g, int base) { deque frontier; frontier.push_back(base); g.dist.insert({{base, base}, 0}); while (!frontier.empty()) { // i love c++ i love c++ i love c++ int from = frontier.front(); int dist = g.dist[{base, from}]; frontier.pop_front(); auto range = g.conns.equal_range(from); for (auto it = range.first; it != range.second; it++) { int to = it->second; if (g.dist.count({base, to}) != 0) continue; g.dist.insert({{base, to}, dist + 1}); frontier.push_back(to); } } } Graph g; int rec(vector &avail, int time1, int time2, int score = 0, int pos1 = 0, int pos2 = 0) { int best = score; if (time1 < time2) { swap(time1, time2); swap(pos1, pos2); } for (int i = 0; i < avail.size(); i++) { int n = avail[i]; if (n == 0) continue; int time1_b = time1 - g.dist[{pos1, n}] - 1; if (time1_b > 0) { avail[i] = 0; int score_b = score + g.rates[n] * time1_b; best = max(best, rec(avail, time1_b, time2, score_b, n, pos2)); avail[i] = n; } } return best; } int main() { vector nonzero; for (string s; getline(cin, s); ) { auto numStart = s.find('=') + 1; auto numEnd = s.find(';', numStart) - numStart; int from = parseID(s.substr(6, 2)); int rate = stoi(s.substr(numStart, numEnd)); g.rates[from] = rate; if (rate != 0) nonzero.push_back(from); s = s.substr(s.find(' ', s.find("valve")) + 1); for (int i = 0; i + 2 <= s.size(); i += 4) { int to = parseID(s.substr(i, 2)); g.conns.insert({from, to}); } } findLengths(g, 0); for (int base : nonzero) findLengths(g, base); cout << rec(nonzero, 30, 0) << endl; cout << rec(nonzero, 26, 26) << endl; }