Acwing345. 牛站

传送门

题目大意

一个 \(T(2\leq T\leq 100)\) 条边的无向图，节点编号 \(1\sim1000\) 求起点 \(S\) 到终点 \(E\) 恰好经过 \(N(2\leq N\leq10^6)\) 的最短路长度。

思路

考虑到边数不到 \(100\) ，于是最多会有 \(200\) 个节点，于是我们可以先将所有节点离散化，然后考虑进行一个类 \(floyd\) 的方法，设 \(f_{a,i,j}\) 为从 \(i\) 到 \(j\) 经过恰好 \(a\) 条边时的最短路，于是有：

每个阶段都相当于是一个距离矩阵，转移的过程相当于将一般矩阵乘法中的运算换成了 \(min\) 和 \(+\) ，于是可以通过矩阵快速幂的方式来快速求出恰好经过 \(N\) 条边时的距离矩阵，复杂度 \(O(T^3logN)\) 。

代码

#include
#include
#include
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using PII = pair;
using PLL = pair;
using TP = tuple;
#define all(x) x.begin(),x.end()
#define mk make_pair
//#define int LL
//#define lc p*2
//#define rc p*2+1
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 210;

struct Edge {
	int from, to;
	LL cost;
}es[maxn];
int N, T, S, E, H[1010], cnt = 0;
sets;
LL d[maxn][maxn], ans[maxn][maxn], tmp[maxn][maxn];

void qpow(int x)
{
	while (x)
	{
		if (x & 1)
		{
			memset(tmp, INF, sizeof(tmp));
			for (int k = 1; k <= cnt; k++)
			{
				for (int i = 1; i <= cnt; i++)
				{
					for (int j = 1; j <= cnt; j++)
						tmp[i][j] = min(tmp[i][j], ans[i][k] + d[k][j]);
				}
			}
			memcpy(ans, tmp, sizeof(ans));
		}
		memset(tmp, INF, sizeof(tmp));
		for (int k = 1; k <= cnt; k++)
		{
			for (int i = 1; i <= cnt; i++)
			{
				for (int j = 1; j <= cnt; j++)
					tmp[i][j] = min(tmp[i][j], d[i][k] + d[k][j]);
			}
		}
		memcpy(d, tmp, sizeof(d));
		x >>= 1;
	}
}

void solve()
{
	memset(d, INF, sizeof(d));
	memset(ans, INF, sizeof(ans));	
	cnt = 0;
	for (auto& a : s)
		H[a] = ++cnt;
	S = H[S], E = H[E];
	for (int i = 1; i <= T; i++)
	{
		d[H[es[i].from]][H[es[i].to]] = min(d[H[es[i].from]][H[es[i].to]], es[i].cost);
		d[H[es[i].to]][H[es[i].from]] = min(d[H[es[i].to]][H[es[i].from]], es[i].cost);
	}
	for (int i = 1; i <= cnt; i++)
		ans[i][i] = 0;
	qpow(N);
	cout << ans[S][E] << endl;
}

int main()
{
	IOS;
	cin >> N >> T >> S >> E;
	for (int i = 1; i <= T; i++)
		cin >> es[i].cost >> es[i].from >> es[i].to, s.insert(es[i].from), s.insert(es[i].to);
	solve();
	return 0;
}