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. struct Solution {
  9.     using sset   = unordered_set<string>;
  10.     using sdpair = pair<string,double>;
  11.     using sdvec  = vector<sdpair>;
  12.     using sdmap  = unordered_map<string,sdvec>;
  13.     bool undefined(const sdmap& mp, const string& var) {
  14.         return mp.find(var) == mp.end(); }
  15.     double dfs(string& src, string& dest, sset& visited, sdmap &mp, double v) {
  16.     	visited.insert(src);
  17.         for (auto [next,w]: mp[src])
  18.         	if (visited.find(next) == visited.end()) {
  19.             	const auto x = v*w;
  20.             	if (next == dest)
  21.                 	return x;
  22.             	const auto y = dfs(next,dest,visited,mp,x);
  23.             	if (y != -1.0)
  24.             		return y; }
  25.     	visited.erase(src); 
  26.         return -1.0; }
  27.     dvec calcEquation(smat& equations, dvec& values, smat& queries) {
  28.         const int N = equations.size(), Q = queries.size();
  29.         sdmap mp;
  30.         for(int i = 0; i < N; ++i) {
  31.             const auto A = equations[i][0], B = equations[i][1];
  32.             const auto v = values[i];
  33.             mp[B].emplace_back(A,v),
  34.             mp[A].emplace_back(B,1.0/v); }
  35.         dvec ans(Q);
  36.         for(int  i = 0; i < Q; ++i) {
  37.         	auto src = queries[i][1], dest = queries[i][0];
  38.         	if (undefined(mp,src) or undefined(mp,dest))
  39.             	ans[i] = -1.0;
  40.             else if (src == dest)
  41.             	ans[i] = 1.0;  	
  42.             else {
  43.             	sset visited;
  44.             	ans[i] = dfs(src,dest,visited,mp,1.0); } }
  45.         return ans; } };
  46.  
  47. int main() {
  48.     const int P = 2;
  49.     int N, Q; cin.tie(nullptr)->sync_with_stdio(false), cin >> N >> Q;
  50.     smat equation(N,svec(P)), query(Q,svec(P));
  51.     dvec value(N);
  52.     for (int i = 0; i < N; ++i)
  53.         cin >> equation[i][0] >> equation[i][1] >> value[i];
  54.     for (int i = 0; i < Q; ++i)
  55.         cin >> query[i][0] >> query[i][1];
  56.     cout << fixed << setprecision(5);
  57.     for (auto ans: Solution().calcEquation(equation,value,query))
  58.         cout << ans << ' ';
  59.     return 0; }
  60.  
Success #stdin #stdout 0.01s 5436KB
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/4iOB0R
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!