oj.uz

Submission #945888

# Submission time Handle Problem Language Result Execution time Memory
945888 2024-03-14T08:26:21 Z ezzzay Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 278 ms 31172 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]);
                ans=min(ans,d[x][j]+d[i][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 210 ms 25032 KB Output is correct
2 Correct 249 ms 23952 KB Output is correct
3 Correct 227 ms 26824 KB Output is correct
4 Correct 226 ms 25028 KB Output is correct
5 Correct 201 ms 24008 KB Output is correct
6 Correct 215 ms 24836 KB Output is correct
7 Correct 217 ms 24048 KB Output is correct
8 Correct 211 ms 24012 KB Output is correct
9 Correct 234 ms 24016 KB Output is correct
10 Correct 244 ms 23816 KB Output is correct
11 Correct 115 ms 19556 KB Output is correct
12 Correct 274 ms 23788 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 26568 KB Output is correct
2 Correct 235 ms 26900 KB Output is correct
3 Correct 232 ms 26564 KB Output is correct
4 Correct 278 ms 26752 KB Output is correct
5 Correct 233 ms 27132 KB Output is correct
6 Correct 239 ms 28160 KB Output is correct
7 Correct 247 ms 31172 KB Output is correct
8 Correct 260 ms 26840 KB Output is correct
9 Correct 241 ms 27136 KB Output is correct
10 Correct 220 ms 27648 KB Output is correct
11 Correct 109 ms 21196 KB Output is correct
12 Correct 250 ms 28640 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 10332 KB Output is correct
2 Incorrect 32 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 210 ms 25032 KB Output is correct
2 Correct 249 ms 23952 KB Output is correct
3 Correct 227 ms 26824 KB Output is correct
4 Correct 226 ms 25028 KB Output is correct
5 Correct 201 ms 24008 KB Output is correct
6 Correct 215 ms 24836 KB Output is correct
7 Correct 217 ms 24048 KB Output is correct
8 Correct 211 ms 24012 KB Output is correct
9 Correct 234 ms 24016 KB Output is correct
10 Correct 244 ms 23816 KB Output is correct
11 Correct 115 ms 19556 KB Output is correct
12 Correct 274 ms 23788 KB Output is correct
13 Correct 231 ms 26568 KB Output is correct
14 Correct 235 ms 26900 KB Output is correct
15 Correct 232 ms 26564 KB Output is correct
16 Correct 278 ms 26752 KB Output is correct
17 Correct 233 ms 27132 KB Output is correct
18 Correct 239 ms 28160 KB Output is correct
19 Correct 247 ms 31172 KB Output is correct
20 Correct 260 ms 26840 KB Output is correct
21 Correct 241 ms 27136 KB Output is correct
22 Correct 220 ms 27648 KB Output is correct
23 Correct 109 ms 21196 KB Output is correct
24 Correct 250 ms 28640 KB Output is correct
25 Correct 42 ms 10332 KB Output is correct
26 Incorrect 32 ms 10332 KB Output isn't correct
27 Halted 0 ms 0 KB -