rt,一开始这样是无法运行的(vscode+devcpp)
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int res = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
res = res * 10 + ch - 48, ch = getchar();
return res * f;
}
const int maxn = 505;
const int maxm = 1000005;
int num[maxm];
int n, m, s, t, e, cnt;
struct mat
{
int a[maxn][maxn];
// inline mat() { memset(a, 0, sizeof a); }
inline mat operator*(const mat &b) const
{
mat c;
memset(c.a, 0x3f, sizeof c.a);
for (register int k = 1; k <= cnt; ++k)
for (register int i = 1; i <= cnt; ++i)
for (register int j = 1; j <= cnt; ++j)
c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
return c;
}
} dis, ans;
inline mat qpow(mat a, int b)
{
mat res=a;
b--;
while (b)
{
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
inline void mem()
{
memset(dis.a, 0x3f, sizeof dis.a);
n = read();
t = read();
s = read();
e = read();
for (register int i = 1, x, y, z; i <= t; ++i)
{
x = read();
y = read();
z = read();
if (!num[y])
num[y] = ++cnt;
if (!num[z])
num[z] = ++cnt;
dis.a[num[y]][num[z]] = dis.a[num[z]][num[y]] = x;
}
return;
}
signed main()
{
mem();
ans = qpow(dis, n);
cout << ans.a[num[s]][num[e]];
}
dev返回3开头的一个大数
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int res = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
res = res * 10 + ch - 48, ch = getchar();
return res * f;
}
const int maxn = 505;
const int maxm = 1000005;
int num[maxm];
int n, m, s, t, e, cnt;
struct mat
{
int a[maxn][maxn];
// inline mat() { memset(a, 0, sizeof a); }
inline mat operator*(const mat &b) const
{
mat c;
memset(c.a, 0x3f, sizeof c.a);
for (register int k = 1; k <= cnt; ++k)
for (register int i = 1; i <= cnt; ++i)
for (register int j = 1; j <= cnt; ++j)
c.a[i][j] = min(c.a[i][j], a[i][k] + b.a[k][j]);
return c;
}
} dis, ans;
inline void qpow(int b)
{
while (b)
{
if (b & 1)
ans = ans * dis;
dis = dis * dis;
b >>= 1;
}
return ;
}
inline void mem()
{
memset(dis.a, 0x3f, sizeof dis.a);
n = read();
t = read();
s = read();
e = read();
for (register int i = 1, x, y, z; i <= t; ++i)
{
x = read();
y = read();
z = read();
if (!num[y])
num[y] = ++cnt;
if (!num[z])
num[z] = ++cnt;
dis.a[num[y]][num[z]] = dis.a[num[z]][num[y]] = x;
}
return;
}
signed main()
{
mem();
ans = dis;
qpow(n - 1);
cout << ans.a[num[s]][num[e]];
}
这样本地可运行 而这样本地也无法运行并提交AC
inline mat qpow(int b)
{
mat res=dis;
mat a=dis;
b--;
while (b)
{
if (b & 1)
res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
而且以前写矩阵快速幂的时候这样也没事 请问这是啥原因(数组不大呀)