这题的关键是问题的转化, 看起来有点像解方程, 其实是图的问题, 简单的套 Floyd–Warshall 就可以了.
const calcEquation = function (equations, values, queries) {
const el = equations.length;
const g = {};
let ei0, ei1, vi;
for (let i = 0; i < el; ++i) {
ei0 = equations[i][0], ei1 = equations[i][1], vi = values[i];
if (!g[ei0]) g[ei0] = {};
if (!g[ei1]) g[ei1] = {};
g[ei0][ei0] = g[ei1][ei1] = 1.0;
g[ei0][ei1] = vi;
g[ei1][ei0] = 1 / vi;
}
const gk = Object.keys(g)
const gl = gk.length;
for (k of gk) {
const gik = Object.keys(g[k])
for (i of gik) {
for (j of gik) {
g[i][j] = g[i][k] * g[k][j];
}
}
}
const r = [];
for (const q of queries) {
g[q[0]] && g[q[0]][q[1]] && r.push(g[q[0]][q[1]]) || r.push(-1.0);
}
return r;
};