rubrik stock share

感觉是印度小哥，但毫无口音，可能也是abi吧。Company A owns 10% of Company B, Company B owns 5% of Company C, Company A owns 2% of Company C。
首先model这个结构，其实就是有向有weight的图，然后给一个target和source，求source owns 多少percent of target。这个要和他讨论一下一些问题，
比如有没有环，有没有ownship加起来大于1的情况，一开始是无环的，然后讨论到有环怎么抛出异常，然后怎么加速（memorized search，
记录每个点own多少percentage的target）


unordered_map<string, vector<pair<string, double>>> share_map; // A owns list of {b: shares}
unordered_map<string, double> memory;

void set_share_map(vector<string, pair<string, double>> &input) {
	for (auto item : input) {
		share_map[item.first].push_back(item.second);
	}
}

double getShare(string A, string B) {
	double res = 0.0;

	unordered_set<string> visited;
	visited.insert(A);
	
	res = dfs(A, B, visited);
	if (res == -1.0) {
		return -1.0;
	} else {
		return res;
	}
}

void dfs(string cur, string target, unordered_set<string> &visited) {
	if (target == cur) {
		return 1.0;
	}
	double res = 0.0;
	if (memory.count(cur) > 0) {
		return memory[cur];
	}
	
	for (int i = 0; i < share_map[cur].size(); i++) {
		if (visited.count(share_map[cur][i].first) == 0) {
			visited.insert(share_map[cur][i].first);
			//try {
				double share = dfs(share_map[cur][i].first, target, visited);
				if (share == -1.0) {
					return -1.0;
				}
				res += share_map[cur][i].second * share;
				visited.erase(share_map[cur][i].first);
			//} catch (const char* msg) {
			//	cerr<<msg<<endl;
			//	return -1.0;
			//}
		} else {
			// todo: error
			// throw "loop detected, invalid input";
			return -1.0;
		}
	}
	memory[cur] = res;
	
	return res;
}