算法
(floyd) $O(n^3)$
直接用floyd求得所有点的最短路,再遍历一遍找出最大值就好了。
C++ 代码
// codeforce每日一题 https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=a;i>=b;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 2e5 + 10, M = N * 2, INF = 0x3f3f3f3f, mod = 1e9 + 7;
int n, m;
int g[11][11], dist[11][11];
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
cin>>n;
rep(i, 1, n)
rep(j, 1, n) cin>>g[i][j];
rep(k, 1, n)
rep(i, 1, n)
rep(j, 1, n)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
int res = 0;
rep(i, 1, n)
rep(j, 1, n)
res = max(res, g[i][j]);
cout<<res<<endl;
return 0;
}