Description：

判断一个数是否含有平方因子。

$1\leqslant testcases\leqslant20,1\leqslant n\leqslant10^{18}$

Solution：

一个数如果有平方因子，大于 $\sqrt[3]n$ 的一定只有一个，因为有两个就会乘爆了，所以可以先筛出 $\sqrt[3]{10^{18}}=10^6$ 的素数来依次判断，如果有一个次数大于 $2$ 就不行了，这样会剩下一个数，这个数要么是一个平方数，要么不含平方因子，因为如果是一个平方数乘一个什么的话那就一定爆了，所以直接开根检验即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 251

int f[MAXN][MAXN];

int ans[MAXN][MAXN];

int c[MAXN];

bool cmp(int a,int b){return c[a] < c[b];}

int s[MAXN],p[MAXN];

int main()

{

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n;++i)scanf("%d",&c[i]);

	for(int i = 1;i <= n;++i)s[i] = i;

	sort(s + 1,s + 1 + n,cmp);

	for(int i = 1;i <= n;++i)p[s[i]] = i;

	int a,b,v;

	memset(f,0x3f,sizeof(f));

	for(int i = 1;i <= n;++i)f[i][i] = 0;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d",&a,&b,&v);

		f[b][a] = f[a][b] = min(f[a][b],v);

	}

	memset(ans,0x3f,sizeof(ans));

	for(int k = 1;k <= n;++k)

	{

		for(int i = 1;i <= n;++i)

		{

			for(int j = 1;j <= n;++j)

			{

				f[i][j] = min(f[i][j],f[i][s[k]] + f[s[k]][j]);

				if(c[i] <= c[s[k]] && c[j] <= c[s[k]])ans[i][j] = min(ans[i][j],f[i][j] + c[s[k]]);

			}

		}

	}

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);

		printf("%d\n",ans[a][b]);

	}

	return 0;

}