#include "walk.h"
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define int long long
#define ep insert
using namespace std;
const int N=1e5+5;
int n,m,a[N],b[N],L[N],R[N],c[N];
set<pair<int,int>> s[2][N];
map<pair<int,int>,int> dis,vis;
vector<pair<int,int>> ad[N],er[N];
void dijkstra(int src){
dis[{src,0}]=0;
priority_queue<vector<int>> pq;
pq.push({0,src,0});
while (!pq.empty()){
int x=pq.top()[1],y=pq.top()[2];
pq.pop();
if (vis[{x,y}]) continue;
//cout<<x<<' '<<y<<endl;
vis[{x,y}]=1;
if (y==0){
if (!s[0][x].empty()){
int to=(*s[0][x].begin()).S;
if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+c[to]){
dis[{x,to}]=dis[{x,y}]+c[to];
pq.push({-dis[{x,to}],x,to});
}
}
if (dis.find({x,m+1})==dis.end() || dis[{x,m+1}]>dis[{x,y}]+b[x]){
dis[{x,m+1}]=dis[{x,y}]+b[x];
pq.push({-dis[{x,m+1}],x,m+1});
}
continue;
}
if (y==m+1){
if (!s[0][x].empty()){
int to=(*--s[0][x].end()).S;
if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+b[x]-c[to]){
dis[{x,to}]=dis[{x,y}]+b[x]-c[to];
pq.push({-dis[{x,to}],x,to});
}
}
if (dis.find({x,0})==dis.end() || dis[{x,0}]>dis[{x,y}]+b[x]){
dis[{x,0}]=dis[{x,y}]+b[x];
}continue;
}
if (dis.find({x,0})==dis.end() || dis[{x,0}]>dis[{x,y}]+c[y]){
dis[{x,0}]=dis[{x,y}]+c[y];
pq.push({-dis[{x,0}],x,0});
}
if (dis.find({x,m+1})==dis.end() || dis[{x,m+1}]>dis[{x,y}]+b[x]-c[y]){
dis[{x,m+1}]=dis[{x,y}]+b[x]-c[y];
pq.push({-dis[{x,m+1}],x,m+1});
}
auto it=s[0][x].upper_bound({c[y],y});
if (it!=s[0][x].end()){
int to=(*it).S;
if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+abs(c[to]-c[y])){
dis[{x,to}]=dis[{x,y}]+abs(c[to]-c[y]);
pq.push({-dis[{x,to}],x,to});
}
}
it=s[0][x].lower_bound({c[y],y});
if (it!=s[0][x].begin()){
int to=(*--it).S;
if (dis.find({x,to})==dis.end() || dis[{x,to}]>dis[{x,y}]+abs(c[to]-c[y])){
dis[{x,to}]=dis[{x,y}]+abs(c[to]-c[y]);
pq.push({-dis[{x,to}],x,to});
}
}
it=s[1][y].upper_bound({a[x],x});
if (it!=s[1][y].end()){
int to=(*it).S;
if (dis.find({to,y})==dis.end() || dis[{to,y}]>dis[{x,y}]+abs(a[to]-a[x])){
dis[{to,y}]=dis[{x,y}]+abs(a[to]-a[x]);
pq.push({-dis[{to,y}],to,y});
}
}
it=s[1][y].lower_bound({a[x],x});
if (it!=s[1][y].begin()){
int to=(*--it).S;
if (dis.find({to,y})==dis.end() || dis[{to,y}]>dis[{x,y}]+abs(a[to]-a[x])){
dis[{to,y}]=dis[{x,y}]+abs(a[to]-a[x]);
pq.push({-dis[{to,y}],to,y});
}
}
}return;
}
long long min_distance(vector<int32_t> x, vector<int32_t> h, vector<int32_t> l, vector<int32_t> r, vector<int32_t> y, int32_t S, int32_t g) {
n=x.size(),m=l.size();
for (int i=0;i<n;i++) a[i+1]=x[i],b[i+1]=h[i];
for (int j=0;j<m;j++) L[j+1]=l[j]+1,R[j+1]=r[j]+1,c[j+1]=y[j];
for (int j=1;j<=m;j++){
ad[L[j]].pb({c[j],j});
er[R[j]].pb({c[j],j});
}
set<pair<int,int>> ms;
for (int i=1;i<=n;i++){
for (auto u:ad[i]) ms.ep(u);
for (auto u:ms){
if (u.F<=b[i]) s[0][i].ep(u),s[1][u.F].ep({a[i],i});
else break;
}
for (auto u:er[i]) ms.erase(u);
}
dijkstra(S+1);
if (dis.find({g+1,0})==dis.end()) return -1;
return dis[{g+1,0}];
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
14428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
14420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
50 ms |
30028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
50 ms |
30028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
14428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
