526互联

2023湖南省赛 F 宝石交易 （Floyd+贪心）

发布时间 2023-10-13 21:24:52作者: ikunhuaji

2023湖南省赛 F 宝石交易

思路：让上下两串宝石串相等，且改变最优

首先，对于它提供的所有改变方法用邻接矩阵存，看成图的边

通过Floyd更新所有可变到的情况，即更新多源最短路

遍历确定s的可能第一更新节点，循环遍历t，并与s比较

相同则跳过，不同就获取上下宝石的最优变化（使相等）

代码中为INF则为无变换可能，退出这一情况

#define int long long
#define ld long double

using namespace std;

const int N = 400, INF = 0x3f3f3f3f;

int g[N + 1][N + 1];


signed main()
{
	int n, m;
	scanf("%lld %lld", &n, &m);

	memset(g, 0x3f, sizeof g);

	for (int i = 1; i <= N; i++)g[i][i] = 0;

	vector<int>s(n + 1);
	vector<int>t(2 * n + 1);

	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &s[i]);
	}

	for (int i = 1; i <= n; i++)
	{
		scanf("%lld", &t[i]);

		t[n + i] = t[i];
	}

	while (m--)
	{
		int a, b, c;
		scanf("%lld %lld %lld", &a,&b, &c);

		g[a][b] = min(g[a][b], c);
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}

	int ans = INT_MAX;
	for (int i = 1; i <= n; i++)
	{
		int l = i, r = i + n - 1;
		int sum = 0;
		bool ok = 1;

		for (int j = l, k = 1; j <= r; j++, k++)
		{
			if (s[k] == t[j])
			{
				continue;
			}
			int u = s[k], v = t[j];
			int mn = min(g[u][v], g[v][u]);
			if (mn == INF)
			{
				ok = 0;
				break;
			}
			sum += mn;
			if (sum >= ans)break;
		}
		if (ok)ans = min(ans, sum);
	}

	if (ans >= INT_MAX)printf("-1");
	else printf("%lld", ans);

	return 0;
}