好久没有写Blog，这个寒假打比赛打得挺顺利的。
正题
Portal
其实是最后不够时间了，这道题两个part我都做过。
如果没有AB两个权值那么就是平面图最小割的问题，转化为最短路就可以解决了，具体做法就是把左下角的空白看成起点，右上角的空白看成终点，如果假设要使一条边不能走相当于穿过这条边，会发现最后的决策其实是新起点到新终点的一条路径。
假若有两个值呢？发现乘积最小值的决策点大致分布在一个下凸包上，每一个决策点代表一种AB，如果不怎么会，就去做做最小乘积生成树或者画框，就可以了。
#include<bits/stdc++.h>
using namespace std;const int N=410;
int n;
int st,ed;
struct edge{int y,next,a,b;
}s[N*N<<1];
struct node{int x;long long d;bool operator<(const node q)const{return d>q.d;}
};
priority_queue<node> f;
long long dis[N*N];
int A[N*N],B[N*N];
int first[N*N],len=0;
long long ans=1e18;void ins(int x,int y,int a,int b){s[++len]=(edge){y,first[x],a,b};first[x]=len;
}pair<int,int> Dijkstra(int ta,int tb){ta=-ta,tb=-tb;while(!f.empty()) f.pop();memset(dis,63,sizeof(dis));f.push((node){st,0});dis[st]=0;A[st]=B[st]=0;while(!f.empty()){node X=f.top();f.pop();if(X.d!=dis[X.x]) continue;if(X.x==ed) break;for(int i=first[X.x];i!=0;i=s[i].next) if(dis[s[i].y]>X.d+1ll*ta*s[i].a+1ll*tb*s[i].b){dis[s[i].y]=X.d+1ll*ta*s[i].a+1ll*tb*s[i].b;A[s[i].y]=A[X.x]+s[i].a,B[s[i].y]=B[X.x]+s[i].b;f.push((node){s[i].y,dis[s[i].y]});}}ans=min(ans,1ll*A[ed]*B[ed]);return make_pair(A[ed],B[ed]);
}void solve(pair<int,int> L,pair<int,int> R){pair<int,int> now=Dijkstra(R.second-L.second,L.first-R.first);if(1ll*(now.first-L.first)*(R.second-L.second)-1ll*(now.second-L.second)*(R.first-L.first)>0) solve(L,now),solve(now,R);else return ;
}int main(){scanf("%d",&n);int x,y;ed=(n-1)*(n-1)+1;for(int i=1;i<n;i++){scanf("%d %d",&x,&y);ins(st,(i-1)*(n-1)+1,x,y);for(int j=1;j<n-1;j++)scanf("%d %d",&x,&y),ins((i-1)*(n-1)+j,(i-1)*(n-1)+j+1,x,y);scanf("%d %d",&x,&y);ins(i*(n-1),ed,x,y);}for(int i=1;i<n;i++) scanf("%d %d",&x,&y),ins(i,ed,x,y);for(int i=2;i<=n-1;i++)for(int j=1;j<n;j++)scanf("%d %d",&x,&y),ins((i-1)*(n-1)+j,(i-2)*(n-1)+j,x,y);for(int i=1;i<n;i++) scanf("%d %d",&x,&y),ins(st,(n-2)*(n-1)+i,x,y);solve(Dijkstra(-1,0),Dijkstra(0,-1));printf("%lld\n",ans);
}