User:Matys~enwiki

1. include <iostream>
2. include <string>
3. include <vector>
4. include <algorithm>
5. include <sstream>
6. include <cstdio>
7. include <cstdlib>
8. include <cctype>
9. include <deque>

using namespace std; vector<string> tok(string s, string si) {

 vector<string> ret;
 for( int p = 0, p2; p < s.size(); p = p2+1 ) {
   p2 = s.find_first_of(si, p);
   if( p2 == -1 ) p2 = s.size();
   if( p2-p > 0 ) ret.push_back( s.substr(p, p2-p) );
 }
 return ret;

} int s2i(string s){int r; sscanf(s.c_str(), "%d", &r); return r;} struct ed{ int f, s; string typ2; }; struct no{ string typ; vector <ed> edges; double v; int hm; }; int find(vector <no> all, string t){ for(int i=0; i<all.size(); i++) if(all[i].typ==t)return i; return -1; } bool check(no t1, string t2){ for(int i=0; i<t1.edges.size(); i++) if(t1.edges[i].typ2==t2)return true; return false; } class MoneyExchange { public: double bestRate(vector <string> rates, string type1, string type2) { vector <no> all; no t1; ed tt1; int i, in; double tr; if(type1==type2)return 1.0; vector <string> tt; string f, s; for(i=0; i<rates.size(); i++){ tt.clear(); t1.typ.erase();t1.edges.clear();t1.v=0.0;t1.hm=0; tt1.f=tt1.s=0;tt1.typ2.erase(); tt=tok(rates[i], " "); if(find(all, tt[0])==-1){ t1.typ=tt[0]; tt1.f=s2i(tt[1]);tt1.s=s2i(tt[3]); tt1.typ2=tt[2]; t1.edges.push_back(tt1); all.push_back(t1); } else{ in=find(all, tt[0]); tt1.f=s2i(tt[1]);tt1.s=s2i(tt[3]); tt1.typ2=tt[2]; all[in].edges.push_back(tt1); } if(find(all, tt[2])==-1){ t1.typ=tt[2]; t1.v=0.0; t1.hm=0; all.push_back(t1); } } in=find(all, type1); if(in==-1)return -1.0; deque <no> Q; if(find(all,type1)==find(all,type2))return 1.0; Q.push_back(all[in]); all[in].hm++; while(!Q.empty()){ no u; u=Q[0];Q.pop_front(); u.hm++; for(i=0; i<u.edges.size(); i++){ if(u.typ==u.edges[i].typ2)continue; in=find(all, u.edges[i].typ2); tr=u.edges[i].s/double(u.edges[i].f); if(u.v!=0)tr*=u.v; if(all[in].v==0 || all[in].hm<all.size()-1 || all[in].v<tr){ if(all[in].v<tr){ all[in].v=tr; all[in].hm++; Q.push_back(all[in]);} } } } in=find(all, type2); if(all[in].v==0.0)return -1.0; return all[in].v; } };