제출 #1346041

#제출 시각아이디문제언어결과실행 시간메모리
1346041MrAndriaText editor (CEOI24_editor)C++20
45 / 100
266 ms141652 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=1e3+5;
vector <pair <pair <int,int> ,int> > adj[N][N];
int a[N];
int b[N];
int n,x,y,l,r,dist[N][N];
map <int,int> pos;
const long long INF=1e16;
void add_edge(int x,int y,int a,int b,int c){
    // cout<<x<<" "<<y<<" "<<a<<" "<<b<<" "<<c<<endl;
    adj[x][y].pb(make_pair(make_pair(a,b),c));
}
void dijkstra(int x,int y){
    set <pair <int,pair <int,int> > > s;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n+2;j++){
            dist[i][j]=INF;
        }
    }
    dist[x][y]=0;
    s.insert(make_pair(0,make_pair(x,y)));
    while(!s.empty()){
        
        auto u=(*(s.begin())).ss.ff;
        auto v=(*(s.begin())).ss.ss;
        // cout<<u<<" "<<v<<endl;
        s.erase(s.begin());
        for(auto idx:adj[u][v]){
            auto to_x=idx.ff.ff;
            auto to_y=idx.ff.ss;
            auto pr=idx.ss;
            if(dist[u][v]+pr<dist[to_x][to_y]){
                s.erase(make_pair(dist[to_x][to_y],make_pair(to_x,to_y)));
                dist[to_x][to_y]=dist[u][v]+pr;
                s.insert(make_pair(dist[to_x][to_y],make_pair(to_x,to_y)));
            }
        }
    }
}
signed main(){
    cin>>n;
    cin>>x>>y;
    cin>>l>>r;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]++;
        b[i]=a[i];
    }
    b[n+1]=y;
    b[n+2]=r;
    sort(b+1,b+n+3);
    for(int i=1;i<=n+2;i++){
        pos[b[i]]=i;
    }
    // ar dagaviwydes weighted edgebi chaamato
    for(int i=1;i<=n;i++){
        // cout<<i<<" "<<pos[a[i]]<<endl;
        for(int j=1;j<=pos[a[i]];j++){
            if(j==1 and j==pos[a[i]]){
                add_edge(i,j,i-1,pos[a[i-1]],1);
                add_edge(i,j,i-1,min(pos[a[i-1]],j),1);
                add_edge(i,j,i+1,1,1);
                add_edge(i,j,i+1,min(pos[a[i+1]],j),1);
                continue;
            }
            if(j==1){
                add_edge(i,j,i-1,pos[a[i-1]],1);
                add_edge(i,j,i-1,min(pos[a[i-1]],j),1);
                add_edge(i,j,i+1,min(pos[a[i+1]],j),1);

                add_edge(i,j,i,j+1,b[j+1]-b[j]);
                continue;
            }
            if(j==pos[a[i]]){
                add_edge(i,j,i-1,min(pos[a[i-1]],j),1);
                add_edge(i,j,i+1,1,1);
                add_edge(i,j,i+1,min(pos[a[i+1]],j),1);



                add_edge(i,j,i,j-1,b[j]-b[j-1]);
                continue;
            }
            add_edge(i,j,i-1,min(pos[a[i-1]],j),1);
            add_edge(i,j,i+1,min(pos[a[i+1]],j),1);
            

            // weighted
            add_edge(i,j,i,j-1,b[j]-b[j-1]);
            add_edge(i,j,i,j+1,b[j+1]-b[j]);

        }
    }
    dijkstra(x,pos[y]);
    cout<<dist[l][pos[r]]<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...