1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
#include <deque>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
int parseID(string s) {
return (s[0] - 'A') * ('Z' - 'A' + 1) + (s[1] - 'A');
}
// Fucking hell.
struct hash_pair {
template<typename T1, typename T2>
size_t operator()(const pair<T1, T2>& p) const
{
auto h1 = hash<T1>{}(p.first);
auto h2 = hash<T1>{}(p.second);
return h1 ^ (h2 << 1);
}
};
struct Graph {
unordered_multimap<int, int> conns;
unordered_map<int, int> rates;
unordered_map<pair<int, int>, int, hash_pair> dist;
};
void findLengths(Graph &g, int base) {
deque<int> 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;
void rec(vector<int> path, vector<int> &avail, int time, int score) {
cout << score << "\t" << time << "\t";
for (int n : path)
cout << n << ",";
cout << endl;
int cur = path.back();
for (int i = 0; i < avail.size(); i++) {
int n = avail[i];
if (n == 0) continue;
avail[i] = 0;
vector<int> path2 = path;
path2.push_back(n);
int time2 = time + g.dist[{cur, n}] + 1;
if (30 < time2) continue;
int score2 = score + g.rates[n] * (30 - time2);
rec(path2, avail, time2, score2);
avail[i] = n;
}
}
int main() {
vector<int> 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);
vector<int> start = {0};
rec(start, nonzero, 0, 0);
}
|
