oj.uz

Submission #1016274

# Submission time Handle Problem Language Result Execution time Memory
1016274 2024-07-07T15:42:47 Z Aiperiii Olympic Bus (JOI20_ho_t4) C++14
26 / 100
 1000 ms 4456 KB 
#include <bits/stdc++.h>
//#define int long long
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int N=5e4+5;
vector <pair <pair <int,int> ,int> > g[2][205];
int p[4][205],dis[4][205],dist[205];
int a[N],b[N],c[N],d[N],used[N];

priority_queue <pair <int,int> > pq;

void djkstra(int n,int tp,int x){
    dis[x][n]=0;
    pq.push({0,n});
    while(!pq.empty()){
        int v=pq.top().ss;
        pq.pop();
        for(auto to : g[tp][v]){
            if(dis[x][to.ff.ff]>dis[x][v]+to.ff.ss){
                dis[x][to.ff.ff]=dis[x][v]+to.ff.ss;
                p[x][to.ff.ff]=to.ss;
                pq.push({dis[x][to.ff.ff],to.ff.ff});
            }
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        g[0][a[i]].pb({{b[i],c[i]},i});
        g[1][b[i]].pb({{a[i],c[i]},i});
    }
    
    for(int i=1;i<=n;i++){
        for(int j=0;j<4;j++){
            dis[j][i]=1e9;
        }
    }
    djkstra(1,0,0);
    djkstra(1,1,1);
    djkstra(n,0,2);
    djkstra(n,1,3);
    /*for(int x=0;x<4;x++){
        for(int i=1;i<=n;i++){
            cout<<dis[x][i]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n";*/
    for(int x=0;x<4;x++){
        for(int i=1;i<=n;i++){
            used[p[x][i]]=1;
        }
    }
    int mn=2e9;
    if(dis[0][n]<1e9 && dis[2][1]<1e9)mn=min(dis[0][n]+dis[2][1],mn);
    
    for(int i=1;i<=m;i++){
        if(!used[i]){
            int new1n=min(dis[0][n],dis[0][b[i]]+dis[3][a[i]]+c[i]);
            int newn1=min(dis[2][1],dis[2][b[i]]+dis[1][a[i]]+c[i]);
            if(new1n<1e9 && newn1<1e9)mn=min(mn,new1n+newn1+d[i]);
        }
        else{
            for(int j=1;j<=n;j++){
                dist[j]=1e9;
            }
            dist[1]=0;
            pq.push({0,1});
            while(!pq.empty()){
                int v=pq.top().ss;
                pq.pop();
                if(v==b[i]){
                    if(dist[a[i]]>dist[b[i]]+c[i]){
                        dist[a[i]]=dist[b[i]]+c[i];
                        pq.push({dist[a[i]],a[i]});
                    }
                }
                for(auto to : g[0][v]){
                    if(to.ss==i)continue;
                    if(dist[to.ff.ff]>dist[v]+to.ff.ss){
                        dist[to.ff.ff]=dist[v]+to.ff.ss;
                        pq.push({dist[to.ff.ff],to.ff.ff});
                    }
                }
            }
            if(dist[n]<1e9){
                int ans=dist[n];
                for(int j=1;j<=n;j++){
                    dist[j]=1e9;
                }
                dist[n]=0;
                pq.push({0,n});
                while(!pq.empty()){
                    int v=pq.top().ss;
                    pq.pop();
                    if(v==b[i]){
                        if(dist[a[i]]>dist[b[i]]+c[i]){
                            dist[a[i]]=dist[b[i]]+c[i];
                            pq.push({dist[a[i]],a[i]});
                        }
                    }
                    for(auto to : g[0][v]){
                        if(to.ss==i)continue;
                        if(dist[to.ff.ff]>dist[v]+to.ff.ss){
                            dist[to.ff.ff]=dist[v]+to.ff.ss;
                            pq.push({dist[to.ff.ff],to.ff.ff});
                        }
                    }
                }
                if(dist[1]<1e9)mn=min(mn,ans+dist[1]+d[i]);
                
            }
        }
    }
    if(mn==2e9)mn=-1;
    cout<<mn<<"\n";
    
}
//g[1]-r
//dis[0] 1
//dis[1] 1r
//dis[2] n
//dis[3] nr

/*

*/

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 382 ms 348 KB Output is correct
4 Correct 465 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 337 ms 596 KB Output is correct
11 Correct 489 ms 348 KB Output is correct
12 Correct 447 ms 344 KB Output is correct
13 Correct 21 ms 348 KB Output is correct
14 Correct 146 ms 348 KB Output is correct
15 Correct 26 ms 344 KB Output is correct
16 Correct 249 ms 572 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 987 ms 4456 KB Output is correct
2 Execution timed out 1056 ms 4444 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 83 ms 3348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 90 ms 4292 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 27 ms 4312 KB Output is correct
9 Correct 31 ms 4188 KB Output is correct
10 Correct 61 ms 4288 KB Output is correct
11 Correct 27 ms 4188 KB Output is correct
12 Correct 30 ms 4188 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 63 ms 4412 KB Output is correct
20 Correct 26 ms 4188 KB Output is correct
21 Correct 31 ms 4300 KB Output is correct
22 Correct 29 ms 4136 KB Output is correct

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 382 ms 348 KB Output is correct
4 Correct 465 ms 344 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 337 ms 596 KB Output is correct
11 Correct 489 ms 348 KB Output is correct
12 Correct 447 ms 344 KB Output is correct
13 Correct 21 ms 348 KB Output is correct
14 Correct 146 ms 348 KB Output is correct
15 Correct 26 ms 344 KB Output is correct
16 Correct 249 ms 572 KB Output is correct
17 Correct 987 ms 4456 KB Output is correct
18 Execution timed out 1056 ms 4444 KB Time limit exceeded
19 Halted 0 ms 0 KB -