題目連結
Observation: Turn this into directed graph!
Consider the following case: $\frac a b = v_1$
- build an edge from a $\rightarrow$ b with weight $v_1$
- build an edge from b $\rightarrow$ a with weight $\frac{1}{v_1}$.
Do the same thing for $\frac b c = v_2$.
Compute $\frac a c$, isn’t it just $v_1 * v_2$, the traversal path from a to c? There you go!
AC Code
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
|
#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
// tree node stuff here...
#endif
static int __initialSetup = []()
{
std::ios::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}
();
// handle special cases first
// [], "", ...
// range of input?
const double oo = 1e9;
class Solution
{
public:
vector<double> calcEquation(vector<pair<string, string>> equations,
vector<double> &values,
vector<pair<string, string>> queries)
{
unordered_map<string, int> cnt;
int idx = 0;
for (auto equation : equations) {
if (cnt.count(equation.first) == 0)
cnt[equation.first] = idx++;
if (cnt.count(equation.second) == 0)
cnt[equation.second] = idx++;
}
double g[idx][idx];
for (int i = 0; i < idx; i++)
for (int j = 0; j < idx; j++)
if (i == j)
g[i][j] = 1;
else
g[i][j] = oo;
for (int i = 0; i < (int)equations.size(); i++) {
int u = cnt[equations[i].first];
int v = cnt[equations[i].second];
// printf("%d %d\n", u, v);
g[u][v] = values[i];
g[v][u] = values[i] == 0 ? 0 : 1 / values[i];
}
// for (int i = 0; i < idx; i++)
// for (int j = 0; j < idx; j++)
// printf("%16.2f%c", g[i][j], j == idx - 1 ? '\n' : ' ');
for (int k = 0; k < idx; k++)
for (int i = 0; i < idx; i++)
for (int j = 0; j < idx; j++)
if (g[i][k] == oo || g[k][j] == oo)
continue;
else
g[i][j] = min(g[i][j], g[i][k] * g[k][j]);
// for (int i = 0; i < idx; i++)
// for (int j = 0; j < idx; j++)
// printf("%16.2f%c", g[i][j], j == idx - 1 ? '\n' : ' ');
vector<double> ans;
for (auto query : queries) {
if (cnt.count(query.first) == 0) {
ans.push_back(-1);
continue;
}
int u = cnt[query.first];
if (cnt.count(query.second) == 0) {
ans.push_back(-1);
continue;
}
int v = cnt[query.second];
if (g[u][v] == oo)
ans.push_back(-1);
else
ans.push_back(g[u][v]);
}
return ans;
}
};
#ifdef LOCAL
int main()
{
return 0;
}
#endif
|