結果
問題 | No.2695 Warp Zone |
ユーザー |
![]() |
提出日時 | 2024-03-22 22:42:05 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,828 bytes |
コンパイル時間 | 2,674 ms |
コンパイル使用メモリ | 217,424 KB |
実行使用メモリ | 19,712 KB |
最終ジャッジ日時 | 2024-09-30 12:07:35 |
合計ジャッジ時間 | 3,946 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <bits/stdc++.h>using namespace std;vector<long long> dijkstra(vector<vector<pair<int, long long>>> &g, int n, int x) {vector<long long> dist(n, 1000000000000000000);vector<bool> visit(n, false);priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> que;dist[x] = 0LL;que.push({dist[x], x});while (!que.empty()) {int v = que.top().second;que.pop();if (visit[v]) {continue;}visit[v] = true;for (auto p : g[v]) {int next_v = p.first;long long d = p.second;if (dist[next_v] > dist[v] + d) {dist[next_v] = dist[v] + d;que.push({dist[next_v], next_v});}}}return dist;}int main() {int h, w, n;cin >> h >> w >> n;vector<int> a(n), b(n), c(n), d(n);for (int i = 0; i < n; i++) {cin >> a[i] >> b[i] >> c[i] >> d[i];}vector<vector<pair<int, long long>>> g(2 * n + 2);int gl = 2 * n + 1;g[0].push_back({gl, (long long)(h - 1 + w - 1)});for (int i = 0; i < n; i++) {int x = 2 * i + 1, y = 2 * i + 2;g[0].push_back({x, (long long)(a[i] - 1 + b[i] - 1)});g[0].push_back({y, (long long)(c[i] - 1 + d[i] - 1)});g[x].push_back({gl, (long long)(h - a[i] + w - b[i])});g[y].push_back({gl, (long long)(h - c[i] + w - d[i])});g[x].push_back({y, 1LL});for (int j = 0; j < n; j++) {if (i == j) {continue;}int x2 = 2 * j + 1;g[y].push_back({x2, (long long)(abs(c[i] - a[j]) + abs(d[i] - b[j]))});}}vector<long long> dist = dijkstra(g, 2 * n + 2, 0);cout << dist[2 * n + 1] << endl;}