結果

問題 No.2897 ２集合間距離
ユーザー 👑 binapbinap
提出日時 2024-05-26 18:35:39
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,104 ms / 3,500 ms
コード長 1,964 bytes
コンパイル時間 2,567 ms
コンパイル使用メモリ 225,060 KB
実行使用メモリ 161,732 KB
最終ジャッジ日時 2024-09-20 20:51:38
合計ジャッジ時間 21,717 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

struct Edge_BFS01{
	int from, to;
	int cost;
	Edge_BFS01(int from, int to, int cost) : from(from), to(to), cost(cost) {};
};

const int INF = 1001001001;
struct BFS01{
	int n, m;
	vector<bool> initialized;
	vector<Edge_BFS01> E;
	vector<vector<int>> G;
	map<int, vector<int>> dist;
	BFS01(int _n) : n(_n), m(0), initialized(n, false), G(n){}
	void add_edge(int from, int to, int cost){
		assert(cost == 0 or cost == 1);
		Edge_BFS01 e(from, to, cost);
		E.push_back(e);
		G[from].emplace_back(m);
		m++;
	}
	void calc(int s){
		initialized[s] = true;
		dist[s] = vector<int>(n, INF);
		deque<tuple<int, int ,int>> de;
		de.emplace_back(0, s, -1);
		while(de.size()){
			auto [cost, from, index] = de.front(); de.pop_front();
			if(dist[s][from] <= cost) continue;
			dist[s][from] = cost;
			for(int index : G[from]){
				int to = E[index].to;
				int cost_plus = E[index].cost;
				if(dist[s][to] <= cost + cost_plus) continue;
				if(cost_plus == 0) de.emplace_front(cost + cost_plus, to, index);
				if(cost_plus == 1) de.emplace_back(cost + cost_plus, to, index);
			}
		}
	}
	int get_dist(int s, int t){
		if(!initialized[s]) calc(s);
		return dist[s][t];
	}
};

const int D = 1000;

int main(){
	auto convert = [&](int x, int y){
		return D * x + y;
	};
	
	BFS01 graph(D * D + 2);
	int sv = D * D;
	int tv = D * D + 1;
	
	int n;
	cin >> n;
	rep(i, n){
		int x, y;
		cin >> x >> y;
		graph.add_edge(sv, convert(x, y), 0);
	}
	int m;
	cin >> m;
	rep(i, m){
		int x, y;
		cin >> x >> y;
		graph.add_edge(convert(x, y), tv, 0);
	}
	rep(x, D) rep(y, D - 1){
		graph.add_edge(convert(x, y), convert(x, y + 1), 1);
		graph.add_edge(convert(x, y + 1), convert(x, y), 1);
	}
	rep(y, D) rep(x, D - 1){
		graph.add_edge(convert(x, y), convert(x + 1, y), 1);
		graph.add_edge(convert(x + 1, y), convert(x, y), 1);
	}
	int ans = graph.get_dist(sv, tv);
	cout << ans << "\n";
	return 0;
}
0