Submission #956467

#	Time	Username	Problem	Language	Result	Execution time	Memory
956467		doducanh	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	460 ms	33916 KiB

commuter_pass

#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=1e15+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;
                q.push(make_pair(dnode+w,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 (stderr)

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:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   80 | main()
      | ^~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45