2 solutions
-
1
floyd算法
#include<bits/stdc++.h> using namespace std; int main() { int n,a[55],b[55]; cin>>n; for(int c=0;c<n;c++) cin>>a[c]>>b[c]; int i[55][55]; for(int c=0;c<n;c++){ for(int d=0;d<c;d++){ i[c][d]=i[d][c]=abs(a[c]-a[d])+abs(b[c]-b[d]); } } for(int k=0;k<n;k++){ for(int c=0;c<n;c++){ for(int d=0;d<n;d++){ i[c][d]=min(i[c][d],max(i[c][k],i[k][d])); } } } int ans=0; for(int c=0;c<n;c++){ for(int d=0;d<c;d++){ ans=max(ans,i[c][d]); } } cout<<(ans+1)/2; }
这道题似乎可以用并查集干 但是我干不来
Information
- ID
- 169
- Time
- 1000ms
- Memory
- 256MiB
- Difficulty
- 6
- Tags
- # Submissions
- 59
- Accepted
- 17
- Uploaded By