結果

問題 No.2695 Warp Zone
ユーザー Yoyoyo8128Yoyoyo8128
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
// push
res.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]);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0