#include "walk.h"
// #pragma GCC optimize("trapv")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define loop(n, i) for (int i = 0; i < n; i++)
#define pb push_back
#define sz(x) (int)(x).size()
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<int32_t> vi32;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef set<ii> sii;
typedef unordered_map<int, int> mii;
int INF = 1e18;
int min_distance(vi32 x, vi32 h, vi32 l, vi32 r, vi32 y, int32_t s, int32_t g)
{
int n = sz(x), m = sz(l);
vector<unordered_map<int, vi>> adj(n);
loop(m, i)
{
for (int p = l[i]; p <= r[i]; p++)
{
if (h[p] < y[i])
continue;
for (int p2 = l[i]; p2 <= r[i]; p2++)
{
if (h[p2] < y[i])
continue;
if (p == p2)
continue;
adj[p][y[i]].pb(p2);
}
}
}
priority_queue<iii, vector<iii>, greater<iii>> q;
vector<mii> disList(n);
auto dis = [&](int p, int y) -> int
{
if (disList[p].count(y))
return disList[p][y];
return INF;
};
q.push({0, s, 0});
while (!q.empty())
{
auto [d, p, y] = q.top();
q.pop();
if (dis(p, y) < d)
continue;
disList[p][y] = d;
for (int p2 : adj[p][y])
{
int d2 = d + abs(x[p2] - x[p]);
if (d2 < dis(p2, y))
{
disList[p2][y] = d2;
q.push({d2, p2, y});
}
}
for (auto [y2, adjY] : adj[p])
{
int d2 = d + abs(y2 - y);
if (d2 < dis(p, y2))
{
disList[p][y2] = d2;
q.push({d2, p, y2});
}
}
}
int res = INF;
for (auto [y, adjY] : adj[g])
{
res = min(res, dis(g, y) + y);
}
if (res == INF)
return -1;
return res;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |