LOJ P10015 扩散题解

每日一题 day49 打卡

Analysis

用dis数组记录每两个点之间的时间，再用一个传递闭包来维护最小的时间就好了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define int long long
 7 #define maxn 50+10
 8 #define rep(i,s,e) for(register int i=s;i<=e;++i)
 9 #define dwn(i,s,e) for(register int i=s;i>=e;--i)
10 using namespace std;
11 inline int read()
12 {
13     int x=0,f=1;
14     char c=getchar();
15     while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();}
16     while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
17     return f*x;
18 }
19 inline void write(int x)
20 {
21     if(x<0) {putchar('-'); x=-x;}
22     if(x>9) write(x/10);
23     putchar(x%10+'0');
24 }
25 int n;
26 int dis[maxn][maxn];
27 struct node
28 {
29     int x,y;
30 }a[maxn];
31 signed main()
32 {
33     n=read();
34     rep(i,1,n) 
35     {
36         a[i].x=read();a[i].y=read();
37         rep(j,1,i-1) dis[i][j]=dis[j][i]=(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y)+1)/2;
38     }
39     rep(k,1,n)
40         rep(i,1,n)
41             rep(j,1,n)
42                 if(dis[i][j]>max(dis[i][k],dis[k][j]))
43                     dis[i][j]=dis[j][i]=max(dis[i][k],dis[k][j]);
44     int ans=0;
45     rep(i,1,n)
46         rep(j,1,n)
47             ans=max(ans,dis[i][j]);
48     write(ans);
49     return 0;
50 }

请各位大佬斧正~~（反正我不认识斧正是什么意思）~~

LOJ P10015 扩散 题解

Analysis

LOJ P10015 扩散题解