| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 597174 | 2022-07-15T16:34:37 Z | lcj | Sky Walking (IOI19_walk) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
long long min_distance(vector<ll> x, vector<ll> h, vector<ll> l, vector<ll> r, vector<ll> y, ll s, ll g) {
ll n = x.size();
ll m = l.size();
vector<vector<pii>> conto(n);
vector<vector<pll>> neighbours(2*m+2);
for (ll i = 0; i < m; i++)
{
conto[l[i]].push_back({y[i], i});
conto[r[i]].push_back({y[i], i+m});
neighbours[i].push_back({i+m, x[r[i]]-x[l[i]]});
}
for (ll i = 0; i < n; i++)
{
if (conto[i].empty()) continue;
sort(all(conto[i]));
auto &mconto = conto[i];
if (i == s && !mconto.empty()) {
neighbours[2*m].push_back({mconto[0].se, mconto[0].fi});
}
if (i == g && !mconto.empty()) {
neighbours[mconto.back().se].push_back({2*m+1, mconto.back().fi});
}
for (ll j = 0; j < conto[i].size()-1; j++)
{
neighbours[mconto[j].se].push_back({mconto[j+1].se, mconto[j+1].fi-mconto[j].fi});
neighbours[mconto[j+1].se].push_back({mconto[j].se, mconto[j+1].fi-mconto[j].fi});
}
}
vector<ll> dist(2*m+2, 1e12);
dist[2*m] = 0;
priority_queue<pll, vector<pll>, greater<pll>> pq;
pq.push({0, 2*m});
while (!pq.empty())
{
pll cur = pq.top();pq.pop();
if (cur.fi > dist[cur.se]) continue;
for (pll nn : neighbours[cur.se]) {
if (dist[nn.fi] > cur.fi + nn.se) {
dist[nn.fi] = cur.fi + nn.se;
pq.push({dist[nn.fi], nn.fi});
}
}
}
if (dist[2*m+1] == 1e12) {
return -1;
}
return dist[2*m+1];
}