結果
| 問題 | No.1323 うしらずSwap |
| ユーザー |
 penguinman
|
| 提出日時 | 2020-12-20 21:01:04 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 20,394 bytes |
| コンパイル時間 | 3,173 ms |
| コンパイル使用メモリ | 255,252 KB |
| 実行使用メモリ | 46,976 KB |
| 最終ジャッジ日時 | 2024-09-21 12:11:38 |
| 合計ジャッジ時間 | 14,721 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 2 ms
6,940 KB |
| testcase_02 | AC | 2 ms
6,940 KB |
| testcase_03 | AC | 2 ms
6,944 KB |
| testcase_04 | AC | 2 ms
6,944 KB |
| testcase_05 | AC | 2 ms
6,944 KB |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | AC | 2 ms
6,940 KB |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | AC | 2 ms
6,940 KB |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | AC | 186 ms
46,848 KB |
| testcase_17 | AC | 262 ms
46,720 KB |
| testcase_18 | AC | 189 ms
46,848 KB |
| testcase_19 | AC | 260 ms
46,720 KB |
| testcase_20 | AC | 200 ms
46,976 KB |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | AC | 178 ms
46,976 KB |
| testcase_27 | AC | 178 ms
46,976 KB |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | AC | 321 ms
46,464 KB |
| testcase_34 | AC | 309 ms
46,720 KB |
| testcase_35 | AC | 310 ms
46,720 KB |
| testcase_36 | AC | 310 ms
46,848 KB |
| testcase_37 | AC | 306 ms
46,848 KB |
| testcase_38 | AC | 317 ms
46,336 KB |
| testcase_39 | AC | 323 ms
46,720 KB |
| testcase_40 | AC | 324 ms
46,720 KB |
| testcase_41 | AC | 334 ms
46,720 KB |
| testcase_42 | AC | 318 ms
46,720 KB |
| testcase_43 | WA | - |
| testcase_44 | WA | - |
| testcase_45 | WA | - |
| testcase_46 | WA | - |
| testcase_47 | WA | - |
| testcase_48 | WA | - |
| testcase_49 | WA | - |
| testcase_50 | WA | - |
| testcase_51 | WA | - |
| testcase_52 | WA | - |
| testcase_53 | WA | - |
| testcase_54 | WA | - |
| testcase_55 | WA | - |
| testcase_56 | WA | - |
| testcase_57 | WA | - |
| testcase_58 | WA | - |
| testcase_59 | AC | 3 ms
6,944 KB |
| testcase_60 | AC | 3 ms
6,940 KB |
| testcase_61 | WA | - |
ソースコード
#include<bits/stdc++.h>
//using namespace std;
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define per(i,j,n) for(int i=(int)(j);(int)(n)<=i;i--)
#define ALL(a) (a).begin(),(a).end()
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(ll)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(ll)(key)))
#define pb emplace_back
#define mp std::make_pair
//
#define endl "\n"
//using std::endl;
using std::cin;
using std::cout;
using ll=long long;
using std::vector;
using std::string;
using std::upper_bound;
using std::lower_bound;
using vi=vector<ll>;
using vii=vector<vi>;
using pii=std::pair<ll,ll>;
//constexpr ll MOD=1e9+7; constexpr ll root=0; constexpr ll coef=0;
//
constexpr ll MOD=998244353; constexpr ll root=3; constexpr ll coef=119;
//constexpr ll MOD=10000000; constexpr ll root=0; constexpr ll coef=0;
//constexpr ll MOD=1e4; constexpr ll root=0; constexpr ll coef=0;
//constexpr ll MOD=1e5; constexpr ll root=0; constexpr ll coef=0;
constexpr ll MAX=3e6;
constexpr ll inf=(1ll<<60);
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
template<typename T>
struct Segment_tree{
ll N;
T mem;
vector<T> node;
Segment_tree(vector<T> &X,T m):mem(m){
ll sz=X.size();
N=1;
while(N<sz) N*=2;
node.resize(2*N-1,mem);
rep(i,0,sz) node[N-1+i]=X[i];
per(i,N-2,0){
node[i]=Compare(node[i*2+1],node[i*2+2]);
}
}
T Compare(T &A,T &B){
return std::min(A,B);
}
void update(ll X,T val){
X+=N-1;
node[X]=val;
while(X>0){
X=(X-1)/2;
node[X]=Compare(node[X*2+1],node[X*2+2]);
}
}
T Query(ll a,ll b,ll now=0,ll l=0,ll r=-1){ //[a,b),[l,r)
if(r<0) r=N;
if(r<=a||b<=l) return mem;
if(a<=l&&r<=b) return node[now];
auto vl=Query(a,b,now*2+1,l,(l+r)/2),vr=Query(a,b,now*2+2,(l+r)/2,r);
return Compare(vl,vr);
}
ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){
if(r<0) r=N;
if(node[now]<val||l>=right||left>=r) return r;
else if(now>=N-1) return l;
ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2);
if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r);
return vl;
}
};
template<typename T>
struct lazy_Segment_tree{
int N;
vector<T> node,lazy;
T INF;
vector<bool> flag;
lazy_Segment_tree(vector<T> X,T Y):INF(Y){
N=1;
while(X.size()>N) N*=2;
node.resize(2*N-1,Y);
lazy.resize(2*N-1);
flag.resize(2*N-1);
rep(i,0,X.size()) node[i+N-1]=X[i];
per(i,N-2,0) node[i]=compare(node[i*2+1],node[i*2+2]);
}
T compare(T X,T Y){
return std::max(X,Y);
}
T plus(T X,int l,int r){
return X;
}
void eval(int now,int l,int r){
if(flag[now]){
if(r-l>1){
flag[now*2+1]=flag[now*2+2]=1;
lazy[now*2+1]=lazy[now*2+2]=lazy[now];
}
node[now]=lazy[now];
flag[now]=0;
}
}
void update(int a,int b,T add,int now=0,int l=0,int r=-1){
if(r<0) r=N;
eval(now,l,r);
if(b<=l||r<=a) return;
if(a<=l&&r<=b){
lazy[now]=add;
flag[now]=1;
eval(now,l,r);
}
else{
update(a,b,add,now*2+1,l,(r+l)/2);
update(a,b,add,now*2+2,(r+l)/2,r);
node[now]=compare(node[now*2+1],node[now*2+2]);
}
}
T Query(int a,int b,int now=0,int l=0,int r=-1){
if(r<0) r=N;
eval(now,l,r);
if(b<=l||r<=a) return INF;
if(a<=l&&r<=b) return node[now];
return compare(Query(a,b,now*2+1,l,(r+l)/2),Query(a,b,now*2+2,(r+l)/2,r));
}
ll lower_bound(ll left,ll right,T val,ll now=0,ll l=0,ll r=-1){
eval(now,l,r);
if(r<0) r=N;
if(node[now]<val||l>=right||left>=r) return r;
else if(now>=N-1) return l;
ll vl=lower_bound(left,right,val,now*2+1,l,(l+r)/2);
if(vl==(l+r)/2) return lower_bound(left,right,val,now*2+2,(l+r)/2,r);
return vl;
}
};
struct Binary_indexed_tree{
int N;
vi bit;
Binary_indexed_tree(int n):N(n){
bit.resize(N+1,0);
}
void add(int x,ll a){
x++;
for(x;x<=N;x+=(x&-x)) bit[x]+=a;
}
ll sum(int x){
x++;
ll ret=0;
for(x;x>0;x-=(x&-x)) ret+=bit[x];
return ret;
}
ll lower_bound(ll X){
if(sum(N)<X) return -1;
ll ret=0,memo=1,sum=0;
while(memo*2<=N) memo*=2;
while(memo>0){
if(memo+ret<=N&&sum+bit[memo+ret]<X){
sum+=bit[memo+ret];
ret+=memo;
}
memo/=2;
}
return ret;
}
};
struct Union_Find{
ll N;
vi par;
vi siz;
Union_Find(int n):N(n){
par.resize(N);
siz.resize(N,1);
rep(i,0,N) par[i]=i;
}
ll root(ll X){
if(par[X]==X) return X;
return par[X]=root(par[X]);
}
bool same(ll X,ll Y){
return root(X)==root(Y);
}
void unite(ll X,ll Y){
X=root(X);
Y=root(Y);
if(X==Y) return;
if(siz[Y]<siz[X]) std::swap(X,Y);
par[X]=Y;
siz[Y]+=siz[X];
siz[X]=0;
}
ll size(ll X){
return siz[root(X)];
}
};
struct Strongly_Connected_Components{
ll N,M;
vii edge,ver;
vi ind;
Strongly_Connected_Components(vii e){
ll n=e.size();
ll m=0;
vii revedge(n);
ind.resize(n);
rep(i,0,n){
m+=e[i].size();
for(auto p:e[i]) revedge[p].pb(i);
}
vi num(n,-1),po(n);
vector<bool> seen(n);
ll cnt=0;
rep(i,0,n){
if(num[i]==-1){
dfs(i,e,num,cnt);
}
}
rep(i,0,n) po[num[i]]=i;
per(i,n-1,0){
ll X=po[i];
if(!seen[X]){
std::queue<ll> que;
vi v;
que.push(X);
seen[X]=1;
while(!que.empty()){
ll now=que.front(); que.pop();
v.pb(now);
ind[now]=ver.size();
for(auto p:revedge[now]){
if(!seen[p]){
seen[p]=1;
que.push(p);
}
}
}
ver.pb(v);
}
}
N=ver.size();
M=0;
edge.resize(N);
rep(i,0,n){
for(auto p:e[i]){
if(ind[i]==ind[p]) continue;
M++;
edge[ind[i]].pb(ind[p]);
}
}
}
void dfs(ll now,vii &e,vi &num,ll &cnt){
num[now]=0;
for(auto next:e[now]){
if(num[next]==-1){
dfs(next,e,num,cnt);
}
}
num[now]=cnt++;
}
};
struct Directed_Gragh{
ll N,M;
vii edge;
Directed_Gragh(vii e):edge(e){
N=edge.size();
rep(i,0,N) M+=edge[i].size();
}
vi sort(){
vi ret;
vi cnt(N);
rep(i,0,N){
for(auto p:edge[i]) cnt[p]++;
}
std::queue<ll> que;
rep(i,0,N){
if(cnt[i]==0) que.push(i);
}
while(!que.empty()){
ll now=que.front(); que.pop();
ret.pb(now);
for(auto next:edge[now]){
cnt[next]--;
if(cnt[next]==0) que.push(next);
}
}
return ret;
}
};
struct Tree{
int N;
vii dp;
vi par;
vi dist;
vi subtree;
vii edge;
Tree(vii E):edge(E){
N=edge.size();
dp.resize(N);
par.resize(N);
dist.resize(N,-1);
for(int i=0;i<N;i++) dp[i].resize(20);
dist[0]=dp[0][0]=0;
std::queue<int> que;
que.push(0);
while(!que.empty()){
int now=que.front(); que.pop();
for(int i=0;i<edge[now].size();i++){
int next=edge[now][i];
if(dist[next]==-1){
dist[next]=dist[now]+1;
que.push(next);
par[next]=now;
dp[next][0]=now;
}
}
}
for(int i=1;i<20;i++){
for(int j=0;j<N;j++) dp[j][i]=dp[dp[j][i-1]][i-1];
}
}
int LCA(int X,int Y){
if(dist[X]<dist[Y]) std::swap(X,Y);
{
int Z=dist[X]-dist[Y];
int i=0;
while(Z){
if(Z&1) X=dp[X][i];
i++;
Z>>=1;
}
}
if(X==Y) return X;
for(int i=19;i>=0;i--){
if(dp[X][i]!=dp[Y][i]){
X=dp[X][i];
Y=dp[Y][i];
}
}
return dp[X][0];
}
void Subtree(){
subtree.resize(N,-1);
dfs(0);
}
void dfs(ll now){
subtree[now]=1;
for(auto next:edge[now]){
if(subtree[next]==-1){
dfs(next);
subtree[now]+=subtree[next];
}
}
}
};
struct max_flow{
struct Edge{
int to,cap,rev;
};
int N;
vector<vector<Edge>> edge;
vector<int> dist,itr;
max_flow(vii e,vii w){
N=e.size();
edge.resize(N);
rep(i,0,N){
rep(j,0,e[i].size()){
edge[i].pb((Edge){(int)e[i][j],(int)w[i][j],(int)edge[e[i][j]].size()});
edge[e[i][j]].pb((Edge){i,0,(int)edge[i].size()-1});
}
}
}
void add_edge(int from,int to,int cap){
edge[from].pb((Edge){to,cap,(int)edge[to].size()});
edge[to].pb((Edge){from,0,(int)edge[from].size()-1});
}
void bfs(int s){
dist.assign(N,-1);
std::queue<int> que;
dist[s]=0;
que.push(s);
while(!que.empty()){
int now=que.front(); que.pop();
for(auto p:edge[now]){
int next=p.to;
if(p.cap>0&&dist[next]<0){
dist[next]=dist[now]+1;
que.push(next);
}
}
}
}
int dfs(int now,int t,int f){
if(now==t) return f;
for(;itr[now]<edge[now].size();itr[now]++){
Edge& p=edge[now][itr[now]];
if(p.cap>0&&dist[now]<dist[p.to]){
int mem=dfs(p.to,t,std::min(f,p.cap));
if(mem>0){
p.cap-=mem;
edge[p.to][p.rev].cap+=mem;
return mem;
}
}
}
return 0;
}
int Query(int s,int t){
int ret=0;
while(1){
bfs(s);
if(dist[t]<0) break;
itr.assign(N,0);
while(1){
int mem=dfs(s,t,(1<<30));
if(mem<=0) break;
ret+=mem;
}
}
return ret;
}
};
struct min_cost_flow{
struct Edge{
int to,cap,rev;
ll cost;
};
int N;
vector<vector<Edge>> edge;
vector<ll> dist,h;
void add_edge(int from,int to,int cap,ll cost){
edge[from].pb((Edge){to,cap,(int)edge[to].size(),cost});
edge[to].pb((Edge){from,0,(int)edge[from].size()-1,-cost});
}
min_cost_flow(vii e,vii m,vii w){
N=e.size();
edge.resize(N);
rep(i,0,N){
rep(j,0,e[i].size()){
add_edge(i,e[i][j],m[i][j],w[i][j]);
}
}
}
void potential(){
h.assign(N,0);
vector<vector<int>> edge2(N);
vii weight(N);
vector<int> cnt(N);
rep(i,0,N){
for(auto e:edge[i]){
if(e.cap>0&&e.cost<0){
edge2[i].pb(e.to);
weight[i].pb(-e.cost);
cnt[e.to]++;
}
}
}
std::queue<ll> que;
rep(i,0,N){
if(cnt[i]==0) que.push(i);
}
vector<int> ver;
while(!que.empty()){
int now=que.front(); que.pop();
ver.pb(now);
for(auto next:edge2[now]){
cnt[next]--;
if(cnt[next]==0) que.push(next);
}
}
per(i,N-1,0){
rep(j,0,edge2[ver[i]].size()){
int next=edge2[ver[i]][j];
h[ver[i]]=std::max(h[ver[i]],h[next]+weight[ver[i]][j]);
}
}
}
ll Query(int s,int t,int f){
ll ret=0;
potential();
while(f){
vi dist(N,inf);
vector<int> memv(N),meme(N);
dist[s]=0;
prique<std::pair<ll,int>> que;
que.push(mp(0,s));
while(!que.empty()){
auto now=que.top().second;
if(dist[now]<que.top().first){
que.pop();
continue;
}
que.pop();
rep(i,0,edge[now].size()){
auto e=edge[now][i];
auto next=e.to;
if(e.cap>0&&dist[next]>dist[now]+h[now]-h[next]+e.cost){
dist[next]=dist[now]+h[now]-h[next]+e.cost;
memv[next]=now;
meme[next]=i;
que.push(mp(dist[next],next));
}
}
}
if(dist[t]==inf) return -1;
int now=t,max=f;
while(now!=s){
auto& e=edge[memv[now]][meme[now]];
max=std::min(max,e.cap);
now=memv[now];
}
f-=max;
now=t;
while(now!=s){
auto& e=edge[memv[now]][meme[now]];
e.cap-=max;
auto& e2=edge[e.to][e.rev];
e2.cap+=max;
now=memv[now];
}
rep(i,0,N) h[i]+=dist[i];
ret+=h[t]*max;
}
return ret;
}
};
struct Fast_Fourier_Transform{
void dft(vector<std::complex<double>> &func,int inverse){
int siz=func.size();
if(siz==1) return;
vector<std::complex<double>> left,right;
rep(i,0,siz/2){
left.pb(func[i*2]);
right.pb(func[i*2+1]);
}
dft(left,inverse);
dft(right,inverse);
std::complex<double> now=1,zeta=std::polar(1.0,inverse*2.0*acos(-1)/siz);
rep(i,0,siz){
func[i]=left[i%(siz/2)]+now*right[i%(siz/2)];
now*=zeta;
}
}
template<typename T>
vector<double> multiply(vector<T> f,vector<T> g){
vector<std::complex<double>> nf,ng;
int siz=1;
while(siz<f.size()+g.size()) siz<<=1;
nf.resize(siz);
ng.resize(siz);
rep(i,0,f.size()) nf[i]=f[i];
rep(i,0,g.size()) ng[i]=g[i];
dft(nf,1);
dft(ng,1);
rep(i,0,siz) nf[i]*=ng[i];
dft(nf,-1);
vector<double> ret(siz);
rep(i,0,siz) ret[i]=nf[i].real()/siz;
return ret;
}
};
struct Numver_Theoretic_Transform{
void dft(vi &func,bool inverse){
int siz=func.size();
if(siz==1) return;
vi left,right;
rep(i,0,siz/2){
left.pb(func[i*2]);
right.pb(func[i*2+1]);
}
dft(left,inverse);
dft(right,inverse);
ll now=1;
ll zeta;
if(inverse) zeta=modpow(root,MOD-1-(MOD-1)/siz,MOD);
else zeta=modpow(root,(MOD-1)/siz,MOD);
rep(i,0,siz){
func[i]=(left[i%(siz/2)]+now*right[i%(siz/2)])%MOD;
now*=zeta;
now%=MOD;
}
}
vi multiply(vi f,vi g){
vi nf,ng;
int siz=1;
while(siz<f.size()+g.size()) siz<<=1;
nf.resize(siz);
ng.resize(siz);
rep(i,0,f.size()) nf[i]=f[i];
rep(i,0,g.size()) ng[i]=g[i];
dft(nf,0);
dft(ng,0);
rep(i,0,siz){
nf[i]*=ng[i];
nf[i]%=MOD;
}
dft(nf,1);
vi ret(siz);
ll div=modpow(siz,MOD-2,MOD);
rep(i,0,siz) ret[i]=nf[i]*div%MOD;
return ret;
}
};
template<typename T>
struct tancomp{
int place(std::pair<T,T> p){
if(p.first<=0&&p.second<0) return 0;
if(p.first>0&&p.second<=0) return 1;
if(p.first==0&&p.second==0) return 2;
if(p.first>=0&&p.second>0) return 3;
return 4;
}
bool operator()(const std::pair<T,T> &l,const std::pair<T,T> &r){
if(place(l)!=place(r)) return place(l)<place(r);
//l.second/l.first<r.second/r.first
return l.second*r.first<l.first*r.second;
}
};
template<typename T>
vector<std::pair<T,T>> Declination_sort(ll N,vector<T> X,vector<T> Y){
vector<std::pair<T,T>> ret(N);
rep(i,0,N){
ret[i]=(mp(X[i],Y[i]));
}
sort(ALL(ret),tancomp<T>());
return ret;
}
vector<pii> Convex_Hull(vector<pii> X){
int N=X.size();
sort(ALL(X));
if(N<=2) return X;
return X;
}
vi fac,finv,inv;
void COMinit() {
fac.resize(MAX);
finv.resize(MAX);
inv.resize(MAX);
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (int i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % MOD;
inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
finv[i] = finv[i - 1] * inv[i] % MOD;
}
}
ll COM(ll n,ll r){
if(n<r||n<0||r<0) return 0;
return fac[n]*finv[r]%MOD*finv[n-r]%MOD;
}
void comp(vi &A){
std::map<ll,ll> memo;
rep(i,0,A.size()) memo[A[i]]=0;
ll cnt=0;
for(auto &p:memo) p.second=cnt++;
rep(i,0,A.size()) A[i]=memo[A[i]];
}
void dec(std::map<ll,ll> &mem,ll X){
mem[X]--;
if(mem[X]==0) mem.erase(X);
}
void print(bool flag){
vector<char> P={
"No",
"Yes"
};
cout<<P[flag]<<endl;
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::random_device rnd;
std::mt19937 mt(rnd());
ll H,W; cin>>H>>W;
vi x(2),y(2);
rep(i,0,2){
cin>>x[i]>>y[i];
x[i]--;
y[i]--;
}
vector<string> S(H);
rep(i,0,H) cin>>S[i];
vector<vii> dist(2,vii(H,vi(W,inf)));
rep(i,0,2){
dist[i][x[i]][y[i]]=0;
std::queue<pii> que;
que.push(mp(x[i],y[i]));
while(!que.empty()){
auto now=que.front(); que.pop();
vi P={0,1,0,-1},Q={1,0,-1,0};
ll p=now.first,q=now.second;
rep(j,0,4){
ll X=p+P[j],Y=q+Q[j];
if(S[X][Y]!='#'&&dist[i][X][Y]>dist[i][p][q]+1){
dist[i][X][Y]=dist[i][p][q]+1;
que.push(mp(X,Y));
}
}
}
}
ll ans=dist[0][x[1]][y[1]];
if(ans==inf){
cout<<-1<<endl;
return 0;
}
ll cnt=0;
rep(i,0,H){
rep(j,0,W){
if(ans==dist[0][i][j]+dist[1][i][j]) cnt++;
}
}
if(cnt==ans+1){
ll edge=0,vert=0;
rep(i,0,H){
rep(j,0,W){
if(dist[0][i][j]!=inf){
vert++;
vi P={0,1,0,-1},Q={1,0,-1,0};
rep(k,0,4){
ll X=i+P[k],Y=j+Q[k];
if(S[X][Y]=='.') edge++;
}
}
}
}
if(edge==(vert-1)*2){
cout<<-1<<endl;
return 0;
}
ll min=inf;
rep(i,0,H){
rep(j,0,W){
if(dist[0][i][j]+dist[1][i][j]!=ans) min=std::min(min,dist[0][i][j]+dist[1][i][j]);
}
}
if(min==inf){
cout<<-1<<endl;
return 0;
}
ans+=min;
}
else ans*=2;
if(ans==inf) ans=-1;
cout<<ans<<endl;
}