oj.uz

Submission #945714

# Submission time Handle Problem Language Result Execution time Memory
945714 2024-03-14T06:37:49 Z ezzzay Commuter Pass (JOI18_commuter_pass) C++14
16 / 100
 281 ms 28328 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 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);
    }
}
signed main(){
    int n,m,s,t,x,y;
    cin>>n>>m>>s>>t>>x>>y;
    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;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 25028 KB Output is correct
2 Correct 248 ms 23976 KB Output is correct
3 Correct 221 ms 26924 KB Output is correct
4 Correct 214 ms 25024 KB Output is correct
5 Correct 235 ms 23976 KB Output is correct
6 Correct 219 ms 24968 KB Output is correct
7 Correct 221 ms 24012 KB Output is correct
8 Correct 231 ms 24292 KB Output is correct
9 Correct 281 ms 24020 KB Output is correct
10 Correct 216 ms 28328 KB Output is correct
11 Correct 100 ms 21848 KB Output is correct
12 Correct 240 ms 28104 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 25292 KB Output is correct
2 Correct 248 ms 25544 KB Output is correct
3 Incorrect 229 ms 25536 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 13912 KB Output is correct
2 Incorrect 4 ms 12380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 25028 KB Output is correct
2 Correct 248 ms 23976 KB Output is correct
3 Correct 221 ms 26924 KB Output is correct
4 Correct 214 ms 25024 KB Output is correct
5 Correct 235 ms 23976 KB Output is correct
6 Correct 219 ms 24968 KB Output is correct
7 Correct 221 ms 24012 KB Output is correct
8 Correct 231 ms 24292 KB Output is correct
9 Correct 281 ms 24020 KB Output is correct
10 Correct 216 ms 28328 KB Output is correct
11 Correct 100 ms 21848 KB Output is correct
12 Correct 240 ms 28104 KB Output is correct
13 Correct 240 ms 25292 KB Output is correct
14 Correct 248 ms 25544 KB Output is correct
15 Incorrect 229 ms 25536 KB Output isn't correct
16 Halted 0 ms 0 KB -