oj.uz

Submission #945904

# Submission time Handle Problem Language Result Execution time Memory
945904 2024-03-14T08:36:23 Z ezzzay Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 316 ms 30740 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
vector<pair<int,int>>v[N];
int n,m,s,t,x,y;
int dist[N];
int tmp[N];
int par[N];
int d[500][500];
bool vis[N];
vector<pair<int,int>>vc;
void dfs(int a){
    vis[a]=1;
    for(auto p:v[a]){
        int b=p.ff;
        int c=p.ss;
        if(vis[b]==0 and dist[b]+c==dist[a])dfs(b);
    }
}
void sbtsk1(){
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    priority_queue<pair<int,int>>q;
    q.push({0,s});
    par[s]=s;
    dist[s]=0;
    vis[s]=1;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
               
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    
    dfs(t);
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    s=y;
    q.push({0,s});
    dist[s]=0;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    int ans=1e16;
    for(int i=1;i<=n;i++){
        if(vis[i]){
           
            ans=min(ans,dist[i]);
        }
    }
    cout<<ans;
}
void sbtsk2(){
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].pb({b,c});
        v[b].pb({a,c});
    }
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    priority_queue<pair<int,int>>q;
    q.push({0,s});
    par[s]=s;
    dist[s]=0;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    while(t!=s){
        v[t].pb({par[t],0});
        v[par[t]].pb({t,0});
        t=par[t];
    }
    for(int i=1;i<=n;i++){
        dist[i]=1e16;
    }
    s=x;
    q.push({0,s});
    par[s]=s;
    dist[s]=0;
    while(!q.empty()){
        int w=-q.top().ff;
        int a=q.top().ss;
        q.pop();
        if(dist[a]<w)continue;
        for(auto p:v[a]){
            int b=p.ff;
            int c=p.ss;
            if(dist[a]+c<dist[b]){
                dist[b]=dist[a]+c;
                par[b]=a;
                q.push({-dist[b],b});
            }
        }
    }
    cout<<dist[y];
}
void subtsk3(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i==j){
                d[i][j]=0;
                continue;
            }
            d[i][j]=1e14;
        }
    }
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        d[a][b]=min(d[a][b],c);
        d[b][a]=min(d[b][a],c);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(d[i][j]> d[i][k]+d[k][j]){
                    d[i][j]=d[i][k]+d[k][j];
                }
            }
        }
    }
    
    int ans=1e14;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            
            if(d[s][i]+d[i][j]+d[j][t]==d[s][t]){
                ans=min(ans,d[x][i]+d[j][y]);
            }
            swap(t,s);
            if(d[s][i]+d[i][j]+d[j][t]==d[s][t]){
                ans=min(ans,d[x][i]+d[j][y]);
            }
            swap(t,s);
            swap(x,y);
            if(d[s][i]+d[i][j]+d[j][t]==d[s][t]){
                ans=min(ans,d[x][i]+d[j][y]);
            }
            swap(x,y);
        }
    }
    cout<<ans;
}
signed main(){
    cin>>n>>m>>s>>t>>x>>y;
     if(n<=300){
        subtsk3();
        return 0;
    }
    if(s==x){
        sbtsk1();
        return 0;
    }
   
    sbtsk2();
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 24904 KB Output is correct
2 Correct 233 ms 23952 KB Output is correct
3 Correct 272 ms 26672 KB Output is correct
4 Correct 260 ms 24992 KB Output is correct
5 Correct 240 ms 23796 KB Output is correct
6 Correct 268 ms 24796 KB Output is correct
7 Correct 246 ms 24108 KB Output is correct
8 Correct 249 ms 24008 KB Output is correct
9 Correct 279 ms 23960 KB Output is correct
10 Correct 257 ms 23780 KB Output is correct
11 Correct 106 ms 19660 KB Output is correct
12 Correct 269 ms 23952 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 26604 KB Output is correct
2 Correct 316 ms 26724 KB Output is correct
3 Correct 257 ms 26328 KB Output is correct
4 Correct 261 ms 26696 KB Output is correct
5 Correct 249 ms 27148 KB Output is correct
6 Correct 260 ms 28072 KB Output is correct
7 Correct 251 ms 30740 KB Output is correct
8 Correct 260 ms 26708 KB Output is correct
9 Correct 297 ms 27024 KB Output is correct
10 Correct 274 ms 26588 KB Output is correct
11 Correct 126 ms 21196 KB Output is correct
12 Correct 264 ms 28372 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 10420 KB Output is correct
2 Incorrect 33 ms 10332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 24904 KB Output is correct
2 Correct 233 ms 23952 KB Output is correct
3 Correct 272 ms 26672 KB Output is correct
4 Correct 260 ms 24992 KB Output is correct
5 Correct 240 ms 23796 KB Output is correct
6 Correct 268 ms 24796 KB Output is correct
7 Correct 246 ms 24108 KB Output is correct
8 Correct 249 ms 24008 KB Output is correct
9 Correct 279 ms 23960 KB Output is correct
10 Correct 257 ms 23780 KB Output is correct
11 Correct 106 ms 19660 KB Output is correct
12 Correct 269 ms 23952 KB Output is correct
13 Correct 274 ms 26604 KB Output is correct
14 Correct 316 ms 26724 KB Output is correct
15 Correct 257 ms 26328 KB Output is correct
16 Correct 261 ms 26696 KB Output is correct
17 Correct 249 ms 27148 KB Output is correct
18 Correct 260 ms 28072 KB Output is correct
19 Correct 251 ms 30740 KB Output is correct
20 Correct 260 ms 26708 KB Output is correct
21 Correct 297 ms 27024 KB Output is correct
22 Correct 274 ms 26588 KB Output is correct
23 Correct 126 ms 21196 KB Output is correct
24 Correct 264 ms 28372 KB Output is correct
25 Correct 50 ms 10420 KB Output is correct
26 Incorrect 33 ms 10332 KB Output isn't correct
27 Halted 0 ms 0 KB -