中文题面：给定一个邻接矩阵，求权值不小于 $m$ 的最短路径长度。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
int n,m;
struct node {
	int a[101][101];
} A,B;
node operator*(const node A,const node B) {
	node C;
	memset(C.a,0,sizeof C.a);
	for(int k=1; k<=n; k++) {
		for(int i=1; i<=n; i++) {
			for(int j=1; j<=n; j++) {
				if(A.a[i][k]&&B.a[k][j])
					C.a[i][j]=max(C.a[i][j],min(m,A.a[i][k]+B.a[k][j]));
			}
		}
	}
	return C;
}
bool check(node A) {
	for(int i=1; i<=n; ++i) {
		if(A.a[1][i]>=m)return 1;
	}
	return 0;
}
node fac[65];
signed main() {
	int R(T);
	while(T--) {
		R(n),R(m);
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				R(A.a[i][j]);
			}
		}
		fac[0]=A;
		int r=-1,ans=0;
		for(int i=1; i<63; ++i) {
			fac[i]=fac[i-1]*fac[i-1];
			if(check(fac[i])) {
				r=i;
				break;
			}
		}
		if(r==-1) {
			cout<<"-1\n";
			continue;
		}
		for(int i=r; i>=0; --i) {
			if(!check(A*fac[i])) {
				A=A*fac[i];
				ans|=(1ll<<i);
			}
		}
		cout<<ans+2<<"\n";
	}
	return 0;
}

這個題是使用矩陣快速幂加速

我們首先發現數據範圍很小，考慮佛洛德，然後佛洛德可能會帶一個倍增或者直接步數的優化

然而我們發現這個 $m$ 過於大了，我們考慮矩陣快速幂加速

如果二分的話時間複雜度是 $O(n^3\log^2n)$ 所以不能使用二分

我們使用倍增，時間複雜度是 $O(n^3\log n)$ 所以我們設 $dp_{l,i,j}$ 表示走 $2^l$ 步，從 $i$ 走到 $j$ 最多的權值是多少

然後我們統計答案就是把這個答案二進位折開，如果不能走就說明還得走，就加上這個東西

#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
#define N 101
using namespace std;
bool Test_MLE_start;
int _=1,n,m,a[N][N];
inline int MIN(int p,int q){return p>q?p:q;}
struct matrix{
	int a[N][N];
	friend matrix operator*(const matrix &A,const matrix &B){
		matrix res;for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) res.a[i][j]=0;
		for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(A.a[i][k]&&B.a[k][j]) res.a[i][j]=MIN(res.a[i][j],A.a[i][k]+B.a[k][j]);
		return res;
	}
}A,pre[N];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("B.in","r",stdin);
//	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
inline bool check(matrix B){
	for(int j=1;j<=n;j++){
		if(B.a[1][j]>=m) return 1;
	}
	return 0;
}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
	_=reads();
	while(_--){
		clr();n=reads(),m=reads();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				A.a[i][j]=reads();
			}
		}
		int R=-1,ans=0;pre[0]=A;
		for(int i=1;i<=63;i++){
			pre[i]=pre[i-1]*pre[i-1];
			if(check(pre[i])){R=i;break;}
		}
		if(R==-1){puts("-1");continue;}
		for(int i=R;i>=0;i--){
			if(!check(A*pre[i])){A=A*pre[i],ans=ans|(1ll<<i);}
		}printf("%lld\n",ans+2);
	}
	return 0;
}

bzoj2165