一个奇怪的问题
查看原帖
一个奇怪的问题
421421
Rem_CandleFire楼主2024/2/26 11:25

这份代码是能够过样例的,

然而,把第awa行的size改成205时测试样例就会本地RE

求大佬解答为什么

#include<bits/stdc++.h>
using namespace std;
const int size=105;//awa
int n,t,S,E;
int cnt,vtx[1000005];
struct matrix{
	long long a[size*2][size*2];
	inline void init()
		{ fill(&a[0][0],&a[204][204],1e9); }
	inline void build()
		{ for(int i=1;i<=cnt;i++) a[i][i]=1; }
}g;
matrix operator *(matrix const &x,matrix const &y)
{
	matrix z;
	z.init();
	for(int k=1;k<=cnt;k++)
		for(int i=1;i<=cnt;i++)
			for(int j=1;j<=cnt;j++)
				z.a[i][j]=min(z.a[i][j],x.a[i][k]+y.a[k][j]);
	return z;
} 
matrix qsm(int n)
{
	matrix ans=g;
	while(n)
	{
		if(n&1)ans=ans*g;
		g=g*g; n>>=1;
	}
	return ans;
} 
int main()
{
	scanf("%d%d%d%d",&n,&t,&S,&E);
	int x,y,z;
	g.init();
	for(int i=1;i<=t;i++)
	{
		scanf("%d%d%d",&z,&x,&y);
		if(!vtx[x])vtx[x]=++cnt;
		if(!vtx[y])vtx[y]=++cnt; 
		x=vtx[x]; y=vtx[y];
		g.a[x][y]=g.a[y][x]=z;
	}
	S=vtx[S]; E=vtx[E];
	matrix ans=qsm(n-1);
	printf("%lld",ans.a[S][E]);

	return 0;
}

2024/2/26 11:25
加载中...