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.  
  8. template<class T, class U>
  9. bool contains(T& container, const U& key) {
  10.     return container.find(key) != container.end(); }
  11.  
  12. struct Solution {
  13.     using sset   = unordered_set<string>;
  14.     using sdpair = pair<string,double>;
  15.     using sdvec  = vector<sdpair>;
  16.     using sdmap  = unordered_map<string,sdvec>;
  17.     using squeue = queue<string>;
  18.     using dqueue = queue<double>;  
  19.     double bfs(sdmap& mp, const string& src, const string& dest) {
  20.         squeue qvar; 
  21.         dqueue qval;
  22.         sset visited; 
  23.     	const auto push = [&](const string& name, double value) {
  24.     		qvar.push(name); 
  25.             qval.push(value); 
  26.             visited.insert(name); };
  27.     	for (push(src,1.0); !qvar.empty(); qvar.pop(), qval.pop()) {
  28.     		const auto x = qvar.front();
  29.     		const auto v = qval.front();
  30.     		for (auto [y,w]: mp[x])
  31.     			if (!contains(visited,y)) {
  32.             		const auto z = v*w;
  33.             		if (y == dest)
  34.                 		return z;
  35.             		push(y,z); } }
  36.     	return -1.0; }
  37.     dvec calcEquation(smat& equations, dvec& values, smat& queries) {
  38.         const int N = equations.size(), Q = queries.size();
  39.         sdmap mp; 
  40.         const auto add_equations = [&](string& A, string& B, double v) {
  41.         	mp[B].emplace_back(A,v);
  42.             mp[A].emplace_back(B,1.0/v); };
  43.         for(int i = 0; i < N; ++i) 
  44.         	add_equations(equations[i][0],equations[i][1],values[i]);
  45.         dvec ans(Q);
  46.         for(int i = 0; i < Q; ++i) {
  47.         	const auto  &src = queries[i][1]; 
  48.             const auto &dest = queries[i][0];
  49.         	if (!contains(mp,src) or !contains(mp,dest))
  50.             	ans[i] = -1.0;
  51.             else if (src == dest)
  52.             	ans[i] = 1.0;  	
  53.             else 
  54.             	ans[i] = bfs(mp,src,dest); }
  55.         return ans; } };
  56.  
  57. int main() {
  58.     const int P = 2;
  59.     int N, Q; cin.tie(nullptr)->sync_with_stdio(false), cin >> N >> Q;
  60.     smat equation(N,svec(P)), query(Q,svec(P));
  61.     dvec value(N);
  62.     for (int i = 0; i < N; ++i)
  63.         cin >> equation[i][0] >> equation[i][1] >> value[i];
  64.     for (int i = 0; i < Q; ++i)
  65.         cin >> query[i][0] >> query[i][1];
  66.     cout << fixed << setprecision(5);
  67.     for (auto ans: Solution().calcEquation(equation,value,query))
  68.         cout << ans << ' ';
  69.     return 0; }
  70.  
Success #stdin #stdout 0.01s 5520KB
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/xoqdMa
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!