AOJ0542 Authentication Level

認証レベル〜
自分にはだいぶ難しかった..
２つの事務所である認証レベルで新たに行ける部屋の数をDijkstraで求めて、事務所1でk個、事務所2でR-k個行ける時の認証レベルの最小値を更新していけばいいです

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<map>
#include<climits>
typedef long long ll;
using namespace std;
int field[500][500],cost[500][500];
int R,W,H,X,Y;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
const int INF  = 1000000000;

struct edge{
	int y,x,cost;
	edge(int y,int x,int cost) : y(y) , x(x) , cost(cost) {}
};
bool operator < (const edge &a,const edge &b){
	return a.cost > b.cost;
}
map<int,int> dijkstra(){
	int x,y,nx,ny,rec;
	map<int,int> foo;
	foo[0] = 0;
	priority_queue<edge> que;
	for(int i = 0; i < H; i++){
		for(int j = 0; j < W; j++){
			cost[i][j] = INT_MAX;
		}
	}
	cost[Y][X] = 1;
	que.push(edge(Y,X,1));
	while(!que.empty()){
		edge crt = que.top();
		que.pop();
		x = crt.x;
		y = crt.y;
		foo[crt.cost]++;
		if(cost[y][x] != crt.cost) continue;
		for(int i = 0; i < 4; i++){
			nx = x + dx[i];
			ny = y + dy[i];
			if(nx == -1 || ny == -1 || nx ==  W || ny == H)continue;
			rec = max(field[ny][nx], crt.cost);
			if(cost[ny][nx] > rec){
				cost[ny][nx] = rec;
				que.push(edge(ny,nx,rec));
			}
		}
	}
	return foo;
}		

int main(){
	while(scanf("%d", &R)){
		if(!R) break;
		vector<ll> a;
		vector<ll> b;
		a.push_back(0);
		b.push_back(0);
		map<int,int> f[2];
		for(int q = 0; q < 2; q++){
			scanf("%d %d %d %d", &W,&H,&X,&Y);
			X--;
			Y--;
			for(int i = 0; i < H; i++){
				for(int j = 0; j < W;j++){
					scanf("%d",&field[i][j]);
				}
			}
			f[q] = dijkstra();
		}
		map<int,int>::iterator it;
		for(it = f[0].begin(); it != f[0].end(); it++){
			for(int i = 0; i < it->second; i++){
				a.push_back(it->first);
			}
		}
		for(it = f[1].begin(); it != f[1].end(); it++){
			for(int i = 0; i < it->second; i++){
				b.push_back(it->first);
			}
		}
		 ll ans = INF;
		 for(int i = 0; i <= R; i++){
			 if (i < a.size() && R - i < b.size()) ans = min(ans,a[i]+b[R-i]);
		 }
		 cout << ans << endl;
	}
		return 0;
}