oj.uz

Submission #945719

# Submission time Handle Problem Language Result Execution time Memory
945719 2024-03-14T06:39:31 Z ezzzay Commuter Pass (JOI18_commuter_pass) C++14
31 / 100
 384 ms 35120 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];
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];
}
signed main(){
    cin>>n>>m>>s>>t>>x>>y;
    if(s==x){
        sbtsk1();
        return 0;
    }
    sbtsk2();
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 25028 KB Output is correct
2 Correct 250 ms 24012 KB Output is correct
3 Correct 285 ms 26928 KB Output is correct
4 Correct 266 ms 25040 KB Output is correct
5 Correct 237 ms 24080 KB Output is correct
6 Correct 266 ms 24856 KB Output is correct
7 Correct 238 ms 24008 KB Output is correct
8 Correct 240 ms 24012 KB Output is correct
9 Correct 301 ms 24108 KB Output is correct
10 Correct 246 ms 24072 KB Output is correct
11 Correct 105 ms 19608 KB Output is correct
12 Correct 315 ms 24028 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 384 ms 26596 KB Output is correct
2 Correct 256 ms 27004 KB Output is correct
3 Correct 234 ms 26444 KB Output is correct
4 Correct 291 ms 30356 KB Output is correct
5 Correct 288 ms 30536 KB Output is correct
6 Correct 333 ms 32040 KB Output is correct
7 Correct 280 ms 35120 KB Output is correct
8 Correct 340 ms 30224 KB Output is correct
9 Correct 289 ms 30596 KB Output is correct
10 Correct 277 ms 30172 KB Output is correct
11 Correct 154 ms 23504 KB Output is correct
12 Correct 252 ms 32156 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 13916 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 25028 KB Output is correct
2 Correct 250 ms 24012 KB Output is correct
3 Correct 285 ms 26928 KB Output is correct
4 Correct 266 ms 25040 KB Output is correct
5 Correct 237 ms 24080 KB Output is correct
6 Correct 266 ms 24856 KB Output is correct
7 Correct 238 ms 24008 KB Output is correct
8 Correct 240 ms 24012 KB Output is correct
9 Correct 301 ms 24108 KB Output is correct
10 Correct 246 ms 24072 KB Output is correct
11 Correct 105 ms 19608 KB Output is correct
12 Correct 315 ms 24028 KB Output is correct
13 Correct 384 ms 26596 KB Output is correct
14 Correct 256 ms 27004 KB Output is correct
15 Correct 234 ms 26444 KB Output is correct
16 Correct 291 ms 30356 KB Output is correct
17 Correct 288 ms 30536 KB Output is correct
18 Correct 333 ms 32040 KB Output is correct
19 Correct 280 ms 35120 KB Output is correct
20 Correct 340 ms 30224 KB Output is correct
21 Correct 289 ms 30596 KB Output is correct
22 Correct 277 ms 30172 KB Output is correct
23 Correct 154 ms 23504 KB Output is correct
24 Correct 252 ms 32156 KB Output is correct
25 Incorrect 22 ms 13916 KB Output isn't correct
26 Halted 0 ms 0 KB -