C++11(clang++ 3.9) 解法, 执行用时: 424ms, 内存消耗: 2552K, 提交时间: 2020-08-29 10:41:18

#include <bits/stdc++.h>
const int N = 110;
 using namespace std;
 const int limits = 1000000;
 typedef pair<int,int> Points;
 const int dx[5] = {0,0,1,-1,0},
           dy[5] = {0,1,0,0,-1};
 #define x first
 #define y second
 #define clr(a,b) memset(a,b,sizeof(a))
 #define For(i,n) for(int i=1;i<=n;i++)
 #define Rep(i,l,r) for(int i=l;i<=r;i++)
 #define Swap(A,B) {Points T = A ; A = T; T = B;}
 int n,npcnt,es,Stack[5*N],head[N*5],dis[5*N],ans;
 set<Points> HASH,farm;
 bool vis[5*N];
 Points p[N],np[5*N];
 struct edge{
     int t,next,w;
 }E[5*N*5*N];
 
 int Len(Points A,Points B){
     return abs(B.x-A.x)+abs(B.y-A.y);
 }
 
 void makelist(int s,int t){
     E[es].t = t; E[es].next = head[s];E[es].w = Len(np[s],np[t]);
     head[s] = es++;
 }
 
 bool inseg(Points out,Points A,Points B){
     if(A.x==B.x)
             if(min(A.y,B.y)<out.y&&out.y<max(A.y,B.y)&&out.x==A.x) return true;
     if(A.y==B.y)
             if(min(A.x,B.x)<out.x&&out.x<max(A.x,B.x)&&out.y==A.y) return true;
     return false;
 }
 
 bool check(Points A,Points B){
     Points C;//   _| 
     if(A.x>B.x) Swap(A,B);
     C.y = A.y; C.x = B.x;
     bool Flag = A.x==B.x||A.y==B.y||farm.find(C)==farm.end();
     For(i,n)
         if(inseg(p[i],A,C)||inseg(p[i],C,B)){
             Flag = false;
             break;
         }
     if(Flag) return true;
     C.x = A.x; C.y = B.y;
     Flag = A.x==B.x||A.y==B.y||farm.find(C)==farm.end();
     For(i,n)
         if(inseg(p[i],A,C)||inseg(p[i],C,B)){
             Flag = false;
             break;
         }
     return Flag;
 }
 
 void init(){
     scanf("%d",&n);
     For(i,n) {
         scanf("%d%d",&p[i].y,&p[i].x);
         HASH.insert(p[i]);farm.insert(p[i]);
         np[i] = p[i];
     }npcnt = n;
     clr(head,-1);
     For(i,n)
         For(j,4){
             int newx = p[i].x + dx[j] , newy = p[i].y + dy[j];
             if(newx<1||newx>limits||newy<1||newy>limits) continue;
             if(HASH.find(make_pair(newx,newy))==HASH.end()) 
             {np[++npcnt] = make_pair(newx,newy);HASH.insert(make_pair(newx,newy));}
         }
     For(i,npcnt-1)
       Rep(j,i+1,npcnt){
             if(check(np[i],np[j])) {
                 makelist(i,j);
                 makelist(j,i);
             }
       } 
 }
 
 int SPFA(int s,int t){
     For(i,5*n) dis[i] = 214748364;
     memset(vis,0,sizeof(vis));
     dis[s] = 0;
     Stack[Stack[0]=1,1] = s;
     while(Stack[0]){
         int First = Stack[Stack[0]--];vis[First] = false;
         for(int p=head[First];p!=-1;p=E[p].next){
             int v = E[p].t;
             if(v<=n&&v!=s&&v!=t) continue;
            if(dis[First]+E[p].w<dis[v]) {
                dis[v] = dis[First] + E[p].w;
                if(!vis[v]) {vis[v] = true; Stack[++Stack[0]] = v;}
            } 
        }  
    }
    return dis[t];
}

void Work(){
    For(i,n){
        int W = SPFA(i,(i==n)?(1):(i+1)); 
        if(W>21474836) puts("-1");
        if(W>21474836) return;
        ans+=W;
    }
    printf("%d\n",ans);
} 

int main(){
    init();
    Work();
}