题解 | #最短路径#

#include<iostream>
#include<string>
using namespace std;
//本题坑点：会重复输入边，本题以第一次输入为准，切忌覆盖
//方法：高精度运算和弗洛伊德
//注意：是无向图
//高精度乘法
//999999999999999999999*2
string mul(string s, int a)
{
	string res = "";
	int carry = 0;
	res = s;
	for (int i = s.length()-1; i >= 0; i--)
	{
		res[i] = ((s[i] - '0') * a + carry) % 10+'0';
		carry = ((s[i] - '0') * a + carry) / 10;
	}
	if (carry > 0)
	{
		res.insert(0, 1, carry + '0');
	}
	return res;
}
//高精度加法
string add(string a, string b)
{
	string res = "";
	int d = a.length() - b.length();
	if (d > 0)
	{
		b.insert(0, d, '0');
	}
	else if(d<0)
	{
		a.insert(0, -d, '0');
	}
	res = a;
	int carry = 0;//进位
	for (int i = a.length() - 1; i >= 0; i--)
	{
		res[i] = char((a[i] - '0' + b[i] - '0' + carry) % 10+'0');
		carry = (a[i] - '0' + b[i] - '0' + carry) / 10;
	}
	if (carry > 0) res.insert(0, 1, carry + '0');
	return res;
}
//比大小(不是字符串大小，而是字符串代表的整数的大小)
//a>b返回true
bool isgreater(string a, string b)
{
	if (a.length() > b.length()) return true;
	else if (a.length() < b.length()) return false;
	else
	{
		for (int i = 0; i < a.length(); i++)
		{
			if (a[i] > b[i]) return true;
			if (a[i] < b[i])return false;
			if (a[i] == b[i])continue;
		}
	}
	return false;
}
int main()
{
	//string s1 = "88888";
	//string s2 = "22";
	////测试高精度乘法
	//cout<<mul(s1, 2)<<endl;
	////测试高精度加法
	//cout << add(s1, s2);
	int cities, roads;
	int from, to;
	//初始化图
	string g[100][100];
	for (int i = 0; i < 100; i++)
		for (int j = 0; j < 100; j++)
			g[i][j] = "INF";//表示此路不通
	while(cin >> cities >> roads)
	{
		//输入边
		string s="1";//第一条边的距离是1
		for (int i = 0; i < roads; i++)
		{
			cin >> from >> to;
			if (i!= 0)
			{
				s = mul(s, 2);
			}
            if(g[from][to]=="INF")//之所以加这个是因为会有重复输入，题目以第一次输入为准
			    g[from][to]= g[to][from] = s;
		}
	}
	//开始弗洛伊德
	for (int k = 0; k < cities; k++)
	{
		for (int i = 0; i < cities; i++)
		{
			for (int j = 0; j < cities; j++)
			{
                if(i==j) continue;
				if (g[i][k] == "INF" || g[k][j] == "INF") continue;
				if (g[i][j] == "INF"||isgreater(g[i][j], add(g[i][k], g[k][j])))
				{
					g[i][j]= add(g[i][k], g[k][j]);
				}
			}
		}
	}
	//处理输出
	for (int i = 1; i < cities; i++)
	{
		if (g[0][i] == "INF") cout << "-1" << endl;
		else if (g[0][i].length() > 5) cout << stoi(g[0][i].substr(g[0][i].length() - 5)) << endl;
		else cout << stoi(g[0][i]) << endl;
	}
}