看到这道题，2个点和一个权值，然后想到图，但是leetcode就是这样，没给数据范围，感觉写起来很费劲，然后就开始用图来做，添加边的时候，注意正向边和反向变，然后查询的时候，先判断2个点是否都出现，然后判断是不是自己到自己，最后用dfs或者bfs到图里面去搜索，第一次交的时候，忘记用vis标记访问过的点，导致tle，加上之后，就ac了，套路一般吧，不知道还有什么trick。
double dfs(vector<vector<pair<int, double> > > &e, int x, int y) {
int n = e.size();
vector<double> dis(n, 1);
queue<int> q;
q.push(x);
vector<bool> tag(n, 0);
while(!q.empty()) {
int u = q.front(); q.pop();
//cout << u << endl;
for (int i = 0; i < e[u].size(); i++) {
int a = e[u][i].first;
double b = e[u][i].second;
if(tag[a]) continue;
dis[a] = dis[u] * b;
if(a == y) return dis[a];
q.push(a);
tag[a] = 1;
}
}
return -1.0;
}
vector<double> calcEquation(vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> query) {
vector<vector<pair<int, double> > > e;
map<string, int> m;
for (int i = 0; i < equations.size(); i++) {
string x = equations[i].first, y = equations[i].second;
if(!m.count(x)) {
vector<pair<int, double> > t;
m[x] = e.size(); e.push_back(t);
}
if(!m.count(y)) {
vector<pair<int, double> > t;
m[y] = e.size(); e.push_back(t);
}
int a = m[x],b = m[y];
e[a].push_back({b, values[i]});
e[b].push_back({a, 1.0 / values[i]});
}
//cout << "ad" << endl;
//cout << e.size() << endl;
vector<double> res;
for (int i = 0; i < query.size(); i++) {
string x = query[i].first, y = query[i].second;
//cout <<x << " " << y << endl;
if(!m.count(x) || !m.count(y)) {
res.push_back(-1.0);
} else {
if(x == y) {
res.push_back(1.0);
} else {
int a = m[x], b = m[y];
double t = dfs(e, a, b);
res.push_back(t);
}
}
}
return res;
}