Submission #2852237

---

Source Code Expand

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <utility>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
const int inf = 1e9;
const ll linf = 1e18;

int h, w;
int sx, sy, gx, gy;
int p[101][101];

typedef struct edge_ {
		int from, to, cost;
		edge_(int f, int t, int c): from(f), to(t), cost(c){};
} edge;

int dx[2] = {-1, 0};
int dy[2] = {0, -1};

vector<edge> vec;

bool comp(const edge &ed1, const edge &ed2){
		return ed1.cost > ed2.cost;
}

int par[10001];
int r[10001];

void init(){
		for(int i = 0; i < 10001; i++){
				par[i] = i;
		}
}

int find(int x){
		if(par[x] == x)return x;
		else return par[x] = find(par[x]);
}

void unite(int x, int y){
		int xp = find(x);
		int yp = find(y);
		if(xp == yp)return;
		if(r[xp] > r[yp]){
				par[yp] = xp;
		}else{
				par[xp] = yp;
				if(r[xp] == r[yp])r[yp]++;
		}
}

int main(int argc, char const* argv[])
{
	cin >> h >> w;
	cin >> sx >> sy >> gx >> gy;
	swap(sx, sy);
	swap(gx, gy);
	ll sum = 0;
	for(int i = 0; i < h; i++){
			for(int j = 0; j < w; j++){
					cin >> p[i][j];
					sum += p[i][j];
					for(int k = 0; k < 2; k++){
							int nx = dx[k] + i;
							int ny = dy[k] + j;
							if(nx >= 0 && nx < h && ny >= 0 && ny < w){
									vec.pb(edge(i * w + j, nx * w + ny, p[i][j] * p[nx][ny]));
							}
					}
			}
	}
	sort(vec.begin(), vec.end(), comp);
	init();
	for(auto itr = vec.begin(); itr != vec.end(); ++itr){
			int from = (*itr).from;
			int to = (*itr).to;
			int cost = (*itr).cost;
			if(find(from) != find(to)){
					sum += cost;
					unite(from, to);
			}
	}
	cout << sum << endl;
	return 0;
}

Submission Info

Judge Result