結果
問題 | No.2695 Warp Zone |
ユーザー |
|
提出日時 | 2024-03-22 21:32:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,374 bytes |
コンパイル時間 | 4,478 ms |
コンパイル使用メモリ | 246,996 KB |
実行使用メモリ | 68,096 KB |
最終ジャッジ日時 | 2024-09-30 10:57:25 |
合計ジャッジ時間 | 5,311 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 WA * 1 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/all>using namespace atcoder;using ll = long long;using ld = long double;using pii = pair<int, int>;using pli = pair<ll, int>;using pll = pair<ll, ll>;typedef vector<ll> vi;typedef vector<vi> vvi;const string Yes = "Yes";const string No = "No";const string YES = "YES";const string NO = "NO";const string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";const ll MOD = 1000000007;const ll mod = 998244353;const long long INF = 1LL << 60;const long double PI = 3.141592653589793;#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#define pb push_back#define mp make_pair#define all(x) (x).begin(), (x).end()#define fi first#define se second#define YESNO(T) \if (T) \{ \cout << "YES" << endl; \} \else \{ \cout << "NO" << endl; \}#define yesno(T) \if (T) \{ \cout << "yes" << endl; \} \else \{ \cout << "no" << endl; \}#define YesNo(T) \if (T) \{ \cout << "Yes" << endl; \} \else \{ \cout << "No" << endl; \}#define inV(vec) \for (ll i = 0; i < vec.size(); i++) \cin >> vec[i];#define outV(vec) \for (ll i = 0; i < vec.size(); i++) \{ \cout << vec[i] << " "; \} \cout << endl;#define print(s) cout << s << endl;template <typename T>inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }template <typename T>inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }// 素因数分解vector<pair<long long, long long>> prime_factorize(long long N){vector<pair<long long, long long>> res;for (long long a = 2; a * a <= N; ++a){if (N % a != 0)continue;long long ex = 0; // 指数// 割れる限り割り続けるwhile (N % a == 0){++ex;N /= a;}// その結果を pushres.push_back({a, ex});}// 最後に残った数についてif (N != 1)res.push_back({N, 1});return res;}using mint = modint998244353;ll mypow(ll a, ll b){ll ans = 1;for (int i = 0; i < b; i++){ans *= a;}return ans;}struct Comb{vector<vector<long long>> com; // 前計算の結果を保存long long p; // p は素数である必要があるvector<ll> fact; // 階乗Comb(long long _p) : p(_p){init(p);}void init(long long p){ // 動的計画法で前処理com.assign(p, vector<long long>(p));com[0][0] = 1;for (int i = 1; i < p; i++){com[i][0] = 1;for (int j = i; j > 0; j--){com[i][j] = (com[i - 1][j - 1] + com[i - 1][j]) % p;}}}long long nCk(long long n, long long k){long long ret = 1;while (n > 0){ // 下から一桁ずつ計算するint ni = n % p;int ki = k % p;ret *= com[ni][ki];ret %= p;n /= p;k /= p;}return ret;}ll modpow(ll a, ll n){if (a == 0){return 0;}ll res = 1;while (n > 0){if (n & 1)res = res * a % p;a = a * a % p;n >>= 1;}return res;}void fac(ll N){fact.pb(1);for (int i = 1; i <= N; i++){ll ppp = i;while (ppp % p == 0){ppp /= p;}fact.pb(fact[i - 1] * (ppp));fact[i] %= p;}}ll Div(ll a, ll b){return (a * modpow(b, p - 2)) % p;}ll nCk2(ll n, ll r){if (n < r){return 0;}if (r < 0){return 0;}if (n < 0){return 0;}return Div(fact[n], fact[r] * fact[n - r] % p);}};// ダイクストラstruct Edge{long long to;long long cost;};void dijkstra(const vector<vector<Edge>> &G, int s, vector<long long> &dis){int N = G.size();dis.resize(N, INF);priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq; // 「仮の最短距離, 頂点」が小さい順に並ぶdis[s] = 0;pq.emplace(dis[s], s);while (!pq.empty()){pair<long long, int> p = pq.top();pq.pop();int v = p.second;if (dis[v] < p.first){ // 最短距離で無ければ無視continue;}for (auto &e : G[v]){if (dis[e.to] > dis[v] + e.cost){ // 最短距離候補なら priority_queue に追加dis[e.to] = dis[v] + e.cost;pq.emplace(dis[e.to], e.to);}}}}int main(){ll H, W, N;cin >> H >> W >> N;vector<ll> A(2*N), B(2*N);for (int i = 0; i < N; i++){cin >> A[2*i] >> B[2*i] >> A[2*i+1] >> B[2*i+1];}vector<vector<Edge>>Gra(2*N+2);for(int i=0;i<2*N;i++){for(int j=0;j<2*N;j++){if(i%2==0 && i+1==j){Gra[i].pb({j,1});}else if(i!=j){Gra[i].pb({j,abs(A[i]-A[j])+abs(B[i]-B[j])});}}Gra[i].pb({2*N,A[i]+B[i]-2});Gra[i].pb({2*N+1,H+W-A[i]-B[i]});Gra[2*N].pb({i,A[i]+B[i]-2});Gra[2*N+1].pb({i,H+W-A[i]-B[i]});}vector<ll>ans(2*N+2,INF);ans[2*N]=0;dijkstra(Gra,2*N,ans);print(ans[2*N+1]);}