https://www.luogu.com.cn/problem/P1522

题目好长图好多…

用 floyd 求各个点的最短路，然后求每个点到各个点的最短路的最长路。然后，枚举所有不连接的点 $i , j$

$\min(f[i]+f[j]+d[i][j])$ 即答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
const int INF=0x3f3f3f3f;
const int MAX=150+10;
int n;
char a[MAX][MAX];
double d[MAX][MAX],f[MAX][MAX],md[MAX],l1,l2;
struct node{
	int x,y;
}p[MAX];
int main(){
	freopen("in","r",stdin);
	sf(n);
	fi(i,1,n+1){
		sf(p[i].x);
		sf(p[i].y);
	}
	fi(i,1,n+1)
		scanf("%s",a[i]+1);
	fi(i,1,n+1)
		fi(j,i+1,n+1){
			d[i][j]=d[j][i]=sqrt((p[i].x-p[j].x) *(p[i].x-p[j].x)+(p[i].y-p[j].y) *(p[i].y-p[j].y) );
			if(a[i][j]=='1')f[i][j]=f[j][i]=d[i][j];
			else f[i][j]=f[j][i]=INF;
		}
	fi(k,1,n+1)  //floyd
		fi(i,1,n+1)
			fi(j,1,n+1)
				if(f[i][j]>f[i][k]+f[k][j])
					f[i][j]=f[i][k]+f[k][j];
	fi(i,1,n+1){  //各个点的最长
		fi(j,1,n+1)
			if(f[i][j]!=INF)
				md[i]=max(md[i],f[i][j]);
		l1 =max(l1,md[i]);
	}
	l2=INF;
	fi(i,1,n+1)
		fi(j,i+1,n+1){
			if(f[i][j]==INF && l2>md[i]+md[j]+d[i][j])
				l2=md[i]+md[j]+d[i][j];
		}
	printf("%.6lf",max(l1,l2));
	return 0;
}