离谱
  • 板块学术版
  • 楼主StarsIntoSea
  • 当前回复13
  • 已保存回复13
  • 发布时间2025/7/28 19:52
  • 上次更新2025/7/29 09:00:10
查看原帖
离谱
1121518
StarsIntoSea楼主2025/7/28 19:52

原题:P2886

下面这份代码是可以正常通过的,但是把第五行的 NN 改成 305 本地就直接 RE,但是交上去还是能正常 AC。

就算把这一行放在 define int long long 的前面也一样。

我一开始还以为是我编译器似了,但是我找别人测结果还是一样的。

求解答。

#include <string.h>
#include <iostream>
using namespace std;
#define int long long
const int N=205;
int n=0,tmp,t,s,e,inf=1e16;
int num[1005];
struct marx{
	int d[N][N];
};
marx mul(marx a,marx b){
	marx s;
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) s.d[i][j]=inf;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			for(int k=1;k<=n;++k)	
				s.d[i][j]=min(s.d[i][j],a.d[i][k]+b.d[k][j]);
	return s;
}

signed main(){
	scanf("%lld%lld%lld%lld",&tmp,&t,&s,&e);
	marx a,b;
	memset(a.d,0x3f,sizeof a.d);
//	for(int i=1;i<=200;++i) for(int j=1;j<=200;++j) a.d[i][j]=b.d[i][j]=inf;
//	for(int i=1;i<=200;++i) a.d[i][i]=b.d[i][i]=0;
	for(int i=1;i<=t;++i){
	    int w,u,v; scanf("%lld%lld%lld",&w,&u,&v);
	    if(!num[u]) num[u]=++n; //离散化
	    if(!num[v]) num[v]=++n;
		a.d[num[u]][num[v]]=a.d[num[v]][num[u]]=w;
	}
	--tmp; b=a;
	while(tmp){
		if(tmp&(int)1) a=mul(a,b);
		b=mul(b,b);
		tmp>>=1;
	}
	printf("%lld\n",a.d[num[s]][num[e]]);
}

2025/7/28 19:52
加载中...