最短路 题解

这里给出一个比较新颖的解法
可以把每个数字看作一个顶点，$u$和$v$之间有路径表示数字$u$能变成数字$v$，最后用乘法原理统计一下就行了。数据范围不大，可用$Floyd$。由于答案可能很大，这里用了高精度

#include<bits/stdc++.h>
using namespace std;

int k,x,y;
bool dp[10][10];
string s,ans="1";
string add(string a,string b)
{
	if (b.size()>a.size()) swap(a,b);
	for (int i=0;i<a.size()-b.size();i++)
		b="0"+b;
	string t="";
	bool carry=0;
	for (int i=b.size()-1;i>=0;i--)
	{
		int r=a[i]-'0'+b[i]-'0'+carry;
		carry=0;
		if (r>=10) carry=1,r-=10;
		string tmp=""; tmp+=r+'0';
		t=tmp+t;
	}
	if (carry) t="1"+t;
	return t;
}
signed main()
{
	cin >> s >> k;
	while (k--)
	{
		cin >> x >> y;
		dp[x][y]=1;
	}
	for (int k=0;k<=9;k++)
	{
		for (int i=0;i<=9;i++)
		{
			for (int j=0;j<=9;j++)
			{
				if (i==j || dp[i][j] || dp[i][k] && dp[k][j])
					dp[i][j]=1;
			}
		}
	}
	for (int i=0;i<s.size();i++)
	{
		int cnt=0;
		for (int j=0;j<=9;j++)
			cnt+=dp[s[i]-'0'][j];
		string tmp=ans;
		cnt--;
		while (cnt--)
			ans=add(ans,tmp);
	}
	cout << ans;
	return 0;
}