本题状态转移方程为f[a+b][i][j] = min(f[a+b][i][j],f[a][i][k] + f[b][k][j])
做的时候一直很疑惑第一维为什么能被优化。
因为在快速幂的第二个参数res的第一维是当前已经经过的边数a,第三个参数g的第一维是转移数组已经经过的边数b
因为很多y总和很多题解都解释过的结合律,所以可以先将g数组自乘,相当于将g经过的边数变大。这样可以更快的将a+b逼近到k这个结果上。
#include <iostream>
using namespace std;
#include <cstring>
#include <map>
const int N = 210;
int k, n, m, S, E;
int g[N][N];
int res[N][N];
void mul(int c[][N], int a[][N], int b[][N])
{
int temp[N][N];
memset(temp, 0x3f, sizeof temp);
for (int k = 1;k <= n;k++)
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
temp[i][j] = min(temp[i][j], a[i][k] + b[k][j]);
memcpy(c, temp, sizeof temp);
}
void qmi()
{
memset(res, 0x3f, sizeof res);
for (int i = 1;i <= n;i++) res[i][i] = 0;
while (k)
{
if (k & 1) mul(res, res, g);
mul(g, g, g);
k >>= 1;
}
}
int main()
{
cin >> k >> m >> S >> E;
memset(g, 0x3f, sizeof g);
map<int, int> ids;
if (!ids.count(S)) ids[S] = ++n;
if (!ids.count(E)) ids[E] = ++n;
S = ids[S], E = ids[E];
while (m--)
{
int a, b, c;
cin >> c >> a >> b;
if (!ids.count(a)) ids[a] = ++n;
if (!ids.count(b)) ids[b] = ++n;
a = ids[a], b = ids[b];
g[a][b] = g[b][a] = min(g[a][b], c);
}
qmi();
cout << res[S][E] << endl;
return 0;
}