@[sjzez__chess](/user/817044)
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int N = 1e5 + 1000, M = 160;
int n;
int X[N], Y[N];
int cnt, id[N];
double dist[M][M];
double mp[N], D[N];
inline double min(double a, double b) { return a < b ? a : b; }
inline double max(double a, double b) { return a > b ? a : b; }
double dis(int a, int b)
{
return sqrt (
(X[a] - X[b]) * (X[a] - X[b])
+
(Y[a] - Y[b]) * (Y[a] - Y[b])
);
}
void dfs(int i)
{
id[i] = cnt;
for (int j = 1; j <= n; j ++ )
if (!id[j] and dist[i][j] != 1e20) dfs(j);
}
signed main()
{
n = read();
for (int i = 1; i <= n; i ++ )
X[i] = read(), Y[i] = read();
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
{
char ch;
while (ch = getchar(), ch != '0' && ch != '1');
if (ch == '1' || i == j) dist[i][j] = dis(i, j);
else dist[i][j] = 1e20;
}
for (int i = 1; i <= n; i ++ )
if (!id[i]) { ++ cnt, dfs(i); }
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
for (int i = 1; i <= n; i ++ )
{
mp[i] = 0.0;
for (int j = 1; j <= n; j ++ )
if (dist[i][j] < 1e20)
mp[i] = max(mp[i], dist[i][j]);
D[id[i]] = max(D[id[i]], mp[i]);
}
double min_d = 1e20, max_d;
for (int i = 1; i <= n; i ++ )
for (int j = i + 1; j <= n; j ++ )
if (id[i] != id[j])
max_d =
max(
max(D[id[i]], D[id[j]]),
mp[i] + dis(i, j) + mp[j]
),
min_d = min(min_d, max_d);
printf("%.6lf\n", min_d);
return 0;
}
```
by bzzltl @ 2023-06-26 19:36:58
@[sjzez__chess](/user/817044) 输入有问题,数据里面还有一个`\r`的换行,所以你那个
```
while (ch = getchar(), ch == ' ' || ch == '\n');
```
要改成
```
while ( ch != '0' || ch != '1')ch = getchar();
```
另外这种题,如果本地运行能过,可以到洛谷在线IDE上试试。
by bzzltl @ 2023-06-26 19:39:24
@[bzzltl](/user/699852) 搜嘎,orz
by sjzez__chess @ 2023-06-26 19:44:02