题意
题目链接
Sol
首先一个结论：floyd算法的正确性与最外层(k)的顺序无关(只要保证是排列即可)
我大概想到一种证明方式就是把最短路树上的链拿出来，不论怎样枚举都会合并其中的两段，所以正确性是对的
这道题的话显然一个(n^4)的暴力是枚举哪个点不选，再跑floyd。
这个暴力等价于求出每个点除它之外的Floyd矩阵
那么考虑暴力分治，每次找一个中间点(mid)，暴力向左右递归即可
时间复杂度：(O(n^3 logn))
代码语言：javascript复制#include<bits/stdc .h>
#define LL long long
using namespace std;
const int MAXN = 301;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 c - '0', c = getchar();
return x * f;
}
int N, g[MAXN][MAXN];
LL ans = 0;
void chmin(int &a, int b) {a = (a < b ? a : b);}
void solve(int l, int r) {
if(l == r) {
for(int i = 1; i <= N; i )
for(int j = 1; j <= N; j )
if(i != l && j != l) ans = (g[i][j] == 1e9 ? -1 : g[i][j]);
return ;
}
int f[MAXN][MAXN];
memcpy(f, g, sizeof(g));
int mid = l r >> 1;
for(int k = mid 1; k <= r; k )
for(int i = 1; i <= N; i )
for(int j = 1; j <= N; j )
if(i != k && j != k) chmin(g[i][j], g[i][k] g[k][j]);
solve(l, mid);
memcpy(g, f, sizeof(g));
for(int k = l; k <= mid; k )
for(int i = 1; i <= N; i )
for(int j = 1; j <= N; j )
if(i != k && j != k) chmin(g[i][j], g[i][k] g[k][j]);
solve(mid 1, r);
memcpy(g, f, sizeof(g));
}
int main() {
N = read();
for(int i = 1; i <= N; i )
for(int j = 1; j <= N; j ) {
g[i][j] = read();
if(g[i][j] == -1) g[i][j] = 1e9;
}
solve(1, N);
cout << ans;
return 0;
}
