题目大意

求在一张有$m$条边无向连通图中，点$s$到点$t$的经过$k$条边的最短路（$1 \leq m \leq 100$，$1 \leq k \leq 10^6$）。

题解

边数$m$很小，显然点数$n$也很小，不超过$200$，我们可以先离散化处理。

我们可以得到$n$个点之间的邻接矩阵，其中矩阵中的$a[i][j]$就相当于点$i$到点$j$的经过$1$条边的最短路。

此时我们设$dp[i][j][k']$表示点$i$到点$j$的经过$k'$条边的最短路，显然有

\[dp[i][j][1] = a[i][j]
\]

且

\[dp[i][j][k'] = \min \{ dp[i][l][k' - 1]+ dp[l][j][k' - 1] \}, k' > 1
\]

显然，朴素的dp复杂度为$O(kn^2)$。

观察这个过程，其实很像矩阵乘法，同样的，我们也可以用矩阵快速幂来优化，这样复杂度就降到$O(n^2 \log{k}) $了。

#include <iostream>

#include <cstring>

#include <algorithm>

#define MAX_M (100 + 5)

using namespace std;

int K, m, s, t;

int u[MAX_M], v[MAX_M];

long long w[MAX_M];

int tmp[MAX_M << 1];

int to[1000005], n;

struct Matrix

{

	long long mat[MAX_M][MAX_M];

	Matrix()

	{

		memset(mat, 0x3f, sizeof mat);

		return;

	}

	friend Matrix operator * (Matrix a, Matrix b)

	{

		Matrix c;

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

		{

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

			{

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

				{

					c.mat[i][j] = min(c.mat[i][j], a.mat[i][k] + b.mat[k][j]);

				}

			}

		}

		return c;

	}

	friend Matrix operator *= (Matrix & a, Matrix b)

	{

		return a = a * b;

	}

};

Matrix a;

int main()

{

	cin >> K >> m >> s >> t;

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

	{

		cin >> w[i] >> u[i] >> v[i];

		tmp[i << 1 ^ 1] = u[i];

		tmp[i << 1] = v[i];

	}

	sort(tmp + 1, tmp + m + m + 1);

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

	{

		if(tmp[i] != tmp[i - 1]) to[tmp[i]] = ++n;

	}

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

	{

		u[i] = to[u[i]];

		v[i] = to[v[i]];

		a.mat[u[i]][v[i]] = min(a.mat[u[i]][v[i]], w[i]);

		a.mat[v[i]][u[i]] = min(a.mat[v[i]][u[i]], w[i]);

	}

	--K;

	Matrix res = a;

	while(K)

	{

		if(K & 1) res *= a;

		a *= a;

		K >>= 1;

	}

	cout << res.mat[to[s]][to[t]];

	return 0;

}

巴特西

【题解】Cow Relays

题目大意

题解

最新文章

热门文章