Solution
mayuan1
2020-08-04 11:15:10
9
返回题目
#include <bits/stdc++.h>
using namespace std;
double dis[200][200], mdis[200];
int x[200], y[200];
int main() {
int n,m;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
dis[i][j] = INT_MAX / 3;
}
for (int u = 1; u <= n; ++u) {
for (int v = 1; v <= n; ++v) {
char c;
cin >> c;
if (c == '1')
dis[u][v] = sqrt((x[u] - x[v]) * (x[u] - x[v]) + (y[u] - y[v]) * (y[u] - y[v]));
}
}
for (int k = 1; k <= n; ++k)
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
if (dis[i][j] > dis[i][k] + dis[k][j])
dis[i][j] = dis[i][k] + dis[k][j];
double ans = 0;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) {
if (dis[i][j] != INT_MAX / 3 && i != j) {
ans = max(ans, dis[i][j]);
mdis[i] = max(mdis[i], dis[i][j]);
}
}
double d = DBL_MAX;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
if (dis[i][j] == INT_MAX / 3 && i != j)
d = min(d, mdis[i] + mdis[j] +
sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) );
cout << fixed << setprecision(6) << max(ans, d) << endl;
return 0;
}
{{ vote && vote.total.up }}