【编程】短最优升级路径 题目描述：游戏网站提供

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <random>
#include <windows.h>

using namespace std;
void Clear_Distances(map<int, set<pair<int, int>>>& distances,int new_node)
{
	map<int, set<pair<int, int>>> temp;
	for (const auto& ps : distances)
	{
		for (const auto& p : ps.second)
		{
			if (p.second != new_node)
			{
				temp[ps.first].insert(pair<int, int>(p.first, p.second));
			}
		}
	}
	distances = temp;
}
//获取新的最短距离，清理并更新Distances，返回始终节点和距离
pair<pair<int,int>,int> find_new_distance(map<int,set<pair<int, int>>>& distances, set<int>& old_nodes)
{
	int Min_Distance = INT_MAX,New_Bgein, New_End;
	bool flag = false;
	pair<pair<int, int>, int> res;
	for (const auto& ps : distances)
	{
		for (const auto& p : ps.second)
		{
			if (old_nodes.find(p.first) != old_nodes.end())
			{
				//清除保存的distances中以新终点为终点的信息
				New_End = p.second;
				res = pair<pair<int, int>, int>(pair<int, int>(p.first, p.second), ps.first);
				flag = true;
				break;
			}
			else if (old_nodes.find(p.second) != old_nodes.end())
			{
				//清除保存的distances中以新终点为终点的信息
				New_End = p.first;
				res = pair<pair<int, int>, int>(pair<int, int>(p.second, p.first), ps.first);
				flag = true;
				break;
			}
		}
		if (flag)
		{
			break;
		}
	}
	Clear_Distances(distances, New_End);
	return res;
	
}
void Get_New_Distances(map<int, map<int, int>>& paths,map<int, set<pair<int, int>>>& new_distance, set<int>& old_nodes, int new_node)
{
	old_nodes.insert(new_node);
	if (paths.find(new_node) != paths.end())
	{
		for (const auto& p : paths[new_node])
		{
			if (old_nodes.find(p.first) == old_nodes.end())
			{
				new_distance[p.second].insert(pair<int, int>(new_node, p.first));
			}
		}
	}
}
//迪杰斯特拉求两点最短路径,返回多维字典 map[begin][end] 为 pair<Pre_Node,distance>
map<int,map<int,pair<int,int>>> Dijkstra(map<int, map<int, int>>& paths,int begin,int end)
{
	int new_node = begin,pre_node,total_distance;
	set<int> old_nodes, new_nodes{begin};
	map<int, map<int, pair<int, int>>> ans;
	//利用红黑树内部存储有序，Distance:<BEGIN，END>
	map<int, set<pair<int,int>>> new_distances;
	while (new_node != end)
	{
		Get_New_Distances(paths, new_distances, old_nodes, new_node);
		if (new_distances.empty())
		{
			break;
		}
		auto BeginEnd_Distance = find_new_distance(new_distances, old_nodes);
		new_node = BeginEnd_Distance.first.second;

		pre_node = BeginEnd_Distance.first.first;
		total_distance = BeginEnd_Distance.second + (ans[begin].find(pre_node) == ans[begin].end() ? 0 : ans[begin][pre_node].second);
		ans[begin][new_node] = pair<int, int>(pre_node, total_distance);
	}
	return ans;
}
//弗洛伊德算法求所有最短路径
map<int, map<int, pair<int, int>>> Floyd(const map<int, map<int, int>>& paths)
{
	//Begin:[End:[Pre,Distance]]
	map<int, map<int, pair<int, int>>> ans;
	set<int> Nodes;
	for (const auto& ps : paths)
	{
		Nodes.insert(ps.first);
		ans[ps.first][ps.first] = pair<int,int>(-1,0);
		for (const auto& p : ps.second)
		{
			Nodes.insert(p.first);
			ans[p.first][p.first] = pair<int, int>(-1, 0);
			ans[ps.first][p.first] = pair<int, int>(ps.first, p.second);
		}
	}
	vector<int> ALL_NODES(Nodes.begin(),Nodes.end());
	int length = ALL_NODES.size();
	int Begin_Node, End_Node, Middle_Node;
	int yuan, zhong1, zhong2;
	for (int k = 0; k < length; k++)
	{
		Middle_Node = ALL_NODES[k];
		for (int i = 0; i < length; i++)
		{
			if (i == k)continue;
			Begin_Node = ALL_NODES[i];
			for (int j = 0; j < length; j++)
			{
				if (j == i || j == k)continue;
				End_Node = ALL_NODES[j];
				yuan = ans[Begin_Node].find(End_Node) == ans[Begin_Node].end() ? INT_MAX : ans[Begin_Node][End_Node].second;
				zhong1 = ans[Begin_Node].find(Middle_Node) == ans[Begin_Node].end() ? INT_MAX : ans[Begin_Node][Middle_Node].second;
				zhong2 = ans[Middle_Node].find(End_Node) == ans[Middle_Node].end() ? INT_MAX : ans[Middle_Node][End_Node].second;
				if (zhong1!=INT_MAX && zhong2!=INT_MAX && yuan>zhong1+zhong2)
				{
					ans[Begin_Node][End_Node].first = Middle_Node;
					ans[Begin_Node][End_Node].second = ans[Begin_Node][Middle_Node].second + ans[Middle_Node][End_Node].second;
				}
			}
		}
	}
	return ans;
}
//非递归深搜
void NonRecursionDFS(map<int, map<int, int>>& paths,const int& begin, const int& target, vector<int>& best_paths, int& min_price)
{
	map<int, map<int, bool>> flags;
	for (const auto& p1 : paths)
	{
		for (const auto& p2 : p1.second)
		{
			flags[p1.first][p2.first] = false;//全都没访问过
		}
	}
	vector<int> My_Stack{ begin }, Now_Paths;
	int total_price;
	while (!My_Stack.empty())
	{
		//出栈元素自己入paths
		int new_version = *(My_Stack.end() - 1);
		My_Stack.pop_back();
		Now_Paths.push_back(new_version);
		if (new_version == target)
		{
			total_price = 0;
			for (int i = 1; i < Now_Paths.size(); i++)
			{
				total_price += paths[Now_Paths[i - 1]][Now_Paths[i]];
			}
			if (total_price < min_price)
			{
				best_paths = Now_Paths;
				min_price = total_price;
			}
		}
		//所有出栈元素能走的下一步入栈
		bool flag = false;//标志没新元素入栈
		if (paths.find(new_version) != paths.end())
		{
			for (const auto& p : paths[new_version])
			{
				My_Stack.push_back(p.first);
				flag = true;
				/*
				if (flags[new_version][p.first] == false)
				{
					flags[new_version][p.first] = true;
					My_Stack.push_back(p.first);
					flag = true;
				}
				*/
			}
		}
		//没有新元素入栈，路径尾已无路可走
		if (flag == false)
		{
			//始终检测最后一个位置是否无路可走，无路可走的出栈
			while (Now_Paths.size()>1 && flag == false)
			{
				int first_last = *(Now_Paths.end() - 1);
				Now_Paths.pop_back();
				int second_last = *(Now_Paths.end() - 1);
				flags[second_last][first_last] = true;
				for (const auto& p : flags[second_last])
				{
					if (p.second == false)
					{
						flag = true;
						break;
					}
				}
			}
			
		}
	}
}
//递归深搜
void RecursionDFS(map<int, map<int, int>>& paths, const int& target, vector<int>& best_paths, vector<int>& now_paths,int now_price , int& min_price)
{
	
	int now_version = *(now_paths.end() - 1);
	if (now_version == target)
	{
		if (now_price < min_price)
		{
			min_price = now_price;
			best_paths = now_paths;
		}
		return;
	}
	if (paths.find(now_version) == paths.end())
	{//不可以继续深入
		return;
	}
	else
	{
		for(const pair<int,int> p:paths[now_version])
		{
			now_paths.push_back(p.first);
			now_price += p.second;
			RecursionDFS(paths, target, best_paths, now_paths, now_price, min_price);
			now_paths.pop_back();
			now_price -= p.second;
		}
	}
}
void get_input(string& s, map<int, map<int, int>>& paths)
{
	int space=0,right,start=0,end=0,price=0;
	right = s.find(' ', space);
	while (space < right)
	{
		start *= 10;
		start += s[space] - '0';
		space++;
	}
	space++;
	right = s.find(' ', space);
	while (space < right)
	{
		end *= 10;
		end += s[space] - '0';
		space++;
	}
	space++;
	while (space < s.length())
	{
		price *= 10;
		price+= s[space] - '0';
		space++;
	}
	paths[start][end]=price;
}

int main()
{
	int begin=1000,end=1050, now_price=0, min_price=INT_MAX;
	int start,target,price;
	map<int, map<int, int>> paths;
	//最小生成树
	string s;
	//cin >> begin >> end;
	vector<int> best_paths, now_paths{begin};
	//getchar();
	//while (getline(cin, s),s != "")
	//{
	//	get_input(s, paths);
	//}
	paths[1000][1020] = 50;
	paths[1000][1030] = 70;
	paths[1020][1030] = 15;
	paths[1020][1040] = 30;
	paths[1030][1050] = 40;
	paths[1040][1050] = 20;
	map<int, map<int, pair<int, int>>> Floyd_Distance = Floyd(paths);
	vector<int> best_nodes{end};
	int distance = Floyd_Distance[begin][end].second;
	while (end != begin)
	{
		end = Floyd_Distance[begin][end].first;
		best_nodes.push_back(end);
	}
	vector<int>::iterator it;
	for (it = best_nodes.end()-1; it > best_nodes.begin(); it--)
	{
		cout << *it << "->";
	}
	cout << *it << "(" << distance << ")"<<endl;
	/*
	RecursionDFS(paths, end, best_paths, now_paths, now_price, min_price);
	int i;
	for (i = 0; i < best_paths.size() - 1; i++)
	{
		cout << best_paths[i] << "->";
	}
	cout << best_paths[i] << "(" << min_price << ")"<<endl;
	best_paths.clear();
	min_price = INT_MAX;
	NonRecursionDFS(paths, begin ,end, best_paths,min_price);
	
	for (i = 0; i < best_paths.size()-1; i++)
	{
		cout << best_paths[i]<<"->";
	}
	cout << best_paths[i]<<"("<<min_price<<")"<<endl;
	*/
}