fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using dvec   = vector<double>;
  5. using svec   = vector<string>;
  6. using smat   = vector<svec>;
  7. using sdpair = pair<string,double>;
  8. using sdvec  = vector<sdpair>;
  9. using sdmap  = unordered_map<string,sdvec>;
  10.  
  11. template<class T, class U>
  12. inline bool contains(T& container, const U& key) {
  13.     return container.find(key) != container.end(); }
  14.  
  15. inline double bfs(sdmap& mp, const string& src, const string& dest) {
  16.     deque<sdpair> q; 
  17.     unordered_set<string> visited; 
  18.     const auto push = [&](const string& name, double value) {
  19.     	q.emplace_back(name,value); 
  20.         visited.insert(name); };
  21.     for (push(src,1.0); !q.empty(); q.pop_front()) {
  22.     	const auto [x,v] = q.front();
  23.     	for (auto [y,w]: mp[x])
  24.     		if (!contains(visited,y)) {
  25.             	const auto z = v*w;
  26.             	if (y == dest)
  27.                 	return z;
  28.             	push(y,z); } }
  29.     return -1.0; }
  30.  
  31. struct Solution {
  32.     inline dvec calcEquation(smat& equations, dvec& values, smat& queries) {
  33.         const int N = equations.size(), Q = queries.size();
  34.         sdmap mp; 
  35.         const auto add_equations = [&](string& A, string& B, double v) {
  36.         	mp[B].emplace_back(A,v);
  37.             mp[A].emplace_back(B,1.0/v); };
  38.         for(int i = 0; i < N; ++i) 
  39.         	add_equations(equations[i][0],equations[i][1],values[i]);
  40.         dvec ans(Q);
  41.         for(int i = 0; i < Q; ++i) {
  42.         	const auto  &src = queries[i][1]; 
  43.             const auto &dest = queries[i][0];
  44.         	if (!contains(mp,src) or !contains(mp,dest))
  45.             	ans[i] = -1.0;
  46.             else if (src == dest)
  47.             	ans[i] = 1.0;  	
  48.             else 
  49.             	ans[i] = bfs(mp,src,dest); }
  50.         return ans; } };
  51.  
  52. int main() {
  53.     const int P = 2;
  54.     int N, Q; cin.tie(nullptr)->sync_with_stdio(false), cin >> N >> Q;
  55.     smat equation(N,svec(P)), query(Q,svec(P));
  56.     dvec value(N);
  57.     for (int i = 0; i < N; ++i)
  58.         cin >> equation[i][0] >> equation[i][1] >> value[i];
  59.     for (int i = 0; i < Q; ++i)
  60.         cin >> query[i][0] >> query[i][1];
  61.     cout << fixed << setprecision(5);
  62.     for (auto ans: Solution().calcEquation(equation,value,query))
  63.         cout << ans << ' ';
  64.     return 0; }
  65.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
3 4
a b 1.5
b c 2.5
bc cd 5.0
a c 
c b
bc cd
cd bc
stdout
copy 
3.75000 0.40000 5.00000 0.20000
https://ideone.com/sMiMSq
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!