結果

問題 No.2695 Warp Zone
コンテスト
ユーザー Aeren
提出日時 2024-03-22 22:12:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 12 ms / 2,000 ms
コード長 4,103 bytes
コンパイル時間 3,013 ms
コンパイル使用メモリ 265,948 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-09-30 11:41:39
合計ジャッジ時間 3,882 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

template<class T>
struct dijkstra_dense{
	int n;
	T base_dist;
	vector<T> dist;
	vector<int> pv;
	vector<int> order;
	vector<int> pos;
	vector<int> root_of;
	vector<int> root;
	vector<int> depth;
	vector<int> was;
	dijkstra_dense(T base_dist = T{0}): base_dist(base_dist){ }
	void init(int n){
		this->n = n;
		dist.assign(n, base_dist);
		pv.assign(n, -1);
		order.clear();
		pos.assign(n, -1);
		root_of.assign(n, -1);
		root.clear();
		depth.assign(n, -1);
		was.assign(n, -2);
		done.assign(n, false);
		attempt = -1;
	}
	int attempt;
	vector<int> done;
	// act_greater(v, u): dist[v] has been updated to larger value by u
	// act_equal(v, u): dist[v] equals the length of shortest path to v through u
	// O(n^2)
	template<class U>
	void _run(const vector<vector<U>> &edge_length, const vector<int> &src, auto act_greater, auto act_equal){
		int n = (int)edge_length.size();
		for(auto u: src){
			if(was[u] == attempt) continue;
			was[u] = attempt;
			done[u] = false;
			dist[u] = base_dist;
			depth[u] = 0;
			root_of[u] = u;
			root.push_back(u);
			pv[u] = -1;
		}
		while(true){
			int u = -1;
			for(auto v = 0; v < n; ++ v) if(was[v] == attempt && !done[v] && (!~u || dist[u] > dist[v])) u = v;
			if(!~u) break;
			done[u] = true;
			pos[u] = (int)order.size();
			order.push_back(u);
			for(auto v = 0; v < n; ++ v) if(~edge_length[u][v]){
				if(was[v] != attempt || !done[v] && dist[u] + edge_length[u][v] < dist[v]){
					dist[v] = dist[u] + edge_length[u][v];
					was[v] = attempt;
					done[v] = false;
					depth[v] = depth[u] + 1;
					pv[v] = u;
					root_of[v] = root_of[u];
					act_greater(v, u);
				}
				else if(!done[v] && dist[u] + edge_length[u][v] == dist[v]) act_equal(v, u);
			}
		}
	}
	// Requires graph
	template<class Graph>
	void run(const Graph &g, const vector<int> &src, auto act_greater, auto act_equal){
		assert(g.n <= n);
		if(g.n == 0) return;
		for(auto u: src) assert(0 <= u && u < g.n);
		root.clear(), order.clear();
		++ attempt;
		vector edge_length(g.n, vector<typename Graph::Weight_t>(g.n, -1));
		for(auto u = 0; u < g.n; ++ u) for(auto id: g.adj[u]){
			if(g.ignore && g.ignore(id)) continue;
			assert(0 <= g.edge[id].cost);
			int v = g(u, id);
			edge_length[u][v] = ~edge_length[u][v] ? min(edge_length[u][v], g.edge[id].cost) : g.edge[id].cost;
		}
		_run(edge_length, src, act_greater, act_equal);
	}
	// Requires graph
	template<class Graph>
	void run(const Graph &g, const vector<int> &src){
		run(g, src, [&](int, int){  }, [&](int, int){  });
	}
	// edge_length = -1 implies no edge
	template<class U>
	void run(const vector<vector<U>> &edge_length, const vector<int> &src, auto act_greater, auto act_equal){
		int n = (int)edge_length.size();
		assert(n <= this->n);
		for(const auto &row: edge_length) for(auto w: row) assert(-1 <= w);
		for(auto u: src) assert(0 <= u && u < n);
		root.clear(), order.clear();
		++ attempt;
		_run(edge_length, src, act_greater, act_equal);
	}
	// edge_length = -1 implies no edge
	template<class U>
	void run(const vector<vector<U>> &edge_length, const vector<int> &src){
		run(edge_length, src, [&](int, int){  }, [&](int, int){  });
	}
	// Check if u is visited during the last dijkstra-like call.
	bool visited(int u) const{
		return was[u] == attempt;
	}
};

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int nr, nc, n;
	cin >> nr >> nc >> n;
	vector<array<int, 4>> a(n + 2);
	a[1] = {nr - 1, nc - 1, nr - 1, nc - 1};
	for(auto &[p, q, r, s]: a | ranges::views::drop(2)){
		cin >> p >> q >> r >> s, -- p, -- q, -- r, -- s;
	}
	vector<vector<int>> adjm(n + 2, vector<int>(n + 2, -1));
	for(auto u = 0; u <= n + 1; ++ u){
		for(auto v = 0; v <= n + 1; ++ v){
			if(u != v){
				adjm[u][v] = abs(a[u][2] - a[v][0]) + abs(a[u][3] - a[v][1]) + 1;
			}
		}
	}
	dijkstra_dense<long long> D;
	D.init(n + 2);
	D.run(adjm, {0});
	cout << D.dist[1] - 1 << "\n";
	return 0;
}

/*

*/
0