oj.uz

Submission #956465

# Submission time Handle Problem Language Result Execution time Memory
956465 2024-04-02T02:51:14 Z doducanh Commuter Pass (JOI18_commuter_pass) C++14
15 / 100
 350 ms 27420 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define ii pair<int,int>
#define ip pair<int,ii>
#define fi first
#define se second
const int maxn=1e5+7;
const int inf=1e18+7;
int vst[maxn];
int du[maxn];
int dv[maxn];
int ds[maxn];
int n,m,s,t,u,v;
int ans;
vector<ii>a[maxn];
int d[2][maxn];
void dijkstra1(int start,int arr[])
{
    for(int i=1;i<=n;i++){vst[i]=0;arr[i]=inf;}
    priority_queue<ii,vector<ii>,greater<ii>>q;
    arr[start]=0;
    q.push({0,start});
    while(q.size()){
        int u=q.top().se;
        int du=q.top().fi;
        q.pop();
        if(vst[u])continue;
        vst[u]=1;
        for(ii p:a[u]){
            int v=p.fi;
            int w=p.se;
            if(arr[v]>arr[u]+w){
                arr[v]=arr[u]+w;
                q.push({arr[v],v});
            }
        }
    }
}
void dijkstra2(int start,int endd)
{

    for(int i=0;i<=n;i++){
        d[0][i]=inf;
        d[1][i]=inf;
        ds[i]=inf;
        vst[i]=0;
    }
    ds[start]=0;
    priority_queue<ip,vector<ip>,greater<ip>>q;
    q.push(make_pair(0,make_pair(start,0)));
    while(q.size()){
        int node=q.top().se.fi;
        int par=q.top().se.se;
        int dnode=q.top().fi;
        q.pop();
        if(vst[node]==0){
            vst[node]=1;
            d[0][node]=min(du[node],d[0][par]);
            d[1][node]=min(dv[node],d[1][par]);
            ds[node]=dnode;
            for(ii p:a[node]){
                int v=p.fi;
                int w=p.se;
                if(ds[v]>ds[node]+w){
                    ds[v]=ds[node]+w;
                    q.push(make_pair(ds[v],make_pair(v,node)));
                }
            }
        }
        else if(dnode==ds[node]){
            if(min(du[node],d[0][par])+min(dv[node],d[1][par])<=d[0][node]+d[1][node])
            {
                d[0][node]=min(d[0][par],du[node]);
                d[1][node]=min(d[1][par],dv[node]);
            }
        }

    }
    ans=min(ans,d[0][endd]+d[1][endd]);
}
main()
{
    cin>>n>>m;
    cin>>s>>t;
    cin>>u>>v;
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        a[x].push_back({y,w});
        a[y].push_back({x,w});
    }
    dijkstra1(u,du);
    dijkstra1(v,dv);
    ans=du[v];
    dijkstra2(s,t);
    dijkstra2(t,s);
    cout<<ans;
    return 0;
}

Compilation message

commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:27:13: warning: unused variable 'du' [-Wunused-variable]
   27 |         int du=q.top().fi;
      |             ^~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   83 | main()
      | ^~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 23752 KB Output is correct
2 Correct 281 ms 20708 KB Output is correct
3 Correct 337 ms 25984 KB Output is correct
4 Correct 278 ms 24628 KB Output is correct
5 Correct 322 ms 23980 KB Output is correct
6 Correct 289 ms 27420 KB Output is correct
7 Incorrect 305 ms 24336 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 307 ms 20712 KB Output is correct
2 Correct 315 ms 21008 KB Output is correct
3 Correct 296 ms 23952 KB Output is correct
4 Correct 299 ms 24128 KB Output is correct
5 Correct 327 ms 23952 KB Output is correct
6 Correct 305 ms 24368 KB Output is correct
7 Correct 318 ms 24164 KB Output is correct
8 Correct 289 ms 23952 KB Output is correct
9 Correct 304 ms 24060 KB Output is correct
10 Correct 309 ms 24180 KB Output is correct
11 Correct 126 ms 14640 KB Output is correct
12 Correct 322 ms 24592 KB Output is correct

Subtask #3
0 / 24.0

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

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 23752 KB Output is correct
2 Correct 281 ms 20708 KB Output is correct
3 Correct 337 ms 25984 KB Output is correct
4 Correct 278 ms 24628 KB Output is correct
5 Correct 322 ms 23980 KB Output is correct
6 Correct 289 ms 27420 KB Output is correct
7 Incorrect 305 ms 24336 KB Output isn't correct
8 Halted 0 ms 0 KB -