Submission #3791976

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)

using namespace std;
typedef long long int ll;
const int MAX_V=10010;
int par[MAX_V]; //親
int height[MAX_V];  //木の深さ

//n要素で初期化
void init (int n){
    for (int i=0;i<n;i++){
        par[i]=i;
        height[i]=0;
    }
}

//木の根を求める
int find (int x){
    if (par[x]==x){
        return x;
    }
    else{
        return par[x] = find(par[x]);
    }
}

//xとyの属する集合を併合
void unite (int x, int y){
    x=find(x);
    y=find(y);
    if (x==y) return;
    
    if (height[x] < height[y]){
        par[x]=y;
    }
    else {
        par[y]=x;
        if (height[x]==height[y]) height[x]++;
    }
}

//xとyが同じ集合に属するか否か
bool same (int x, int y){
    return find(x) == find(y);
}

struct edge {int u, v, cost; };

bool comp(const edge& e1, const edge& e2){
    return e1.cost > e2.cost;
}

vector<edge> es;
int V, E/*, p[100][100]*/;

int kruscal(){
    sort(es.begin(), es.begin()+E, comp); //edge.costが小さい順にソート
    init(V);
    int res=0;
    rep(i,0,E){
        edge e=es[i];
        if (!same(e.u, e.v)){
            unite(e.u, e.v);
            res+=e.cost;
        }
    }
    return res;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int H,W,Sx,Sy,Gx,Gy;
    cin>>H>>W;
    cin>>Sx>>Sy;
    cin>>Gx>>Gy;
    Sx--;Sy--;Gx--;Gy--;
    int sum=0;
    int p[H][W];
    rep(i,0,H){
        rep(j,0,W){
            cin>>p[i][j];
            sum+=p[i][j];
        }
    }
    V=H*W;
    E=2*V-H-W;
    rep(i,0,H){
        rep(j,0,W-1){
            es.push_back(edge{W*i+j,W*i+j+1,p[i][j]*p[i][j+1]});
        }
    }
    rep(i,0,H-1){
        rep(j,0,W){
            es.push_back(edge{W*i+j,W*i+j+W,p[i][j]*p[i+1][j]});
        }
    }
    cout<<kruscal()+sum<<"\n";
}

Submission Info

Judge Result