Submission #434293

#	Time	Username	Problem	Language	Result	Execution time	Memory
434293		JovanK26	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	729 ms	27436 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;
long long n,m,s,t,u,v;
vector< pair<long long,long long> > adj[100001];
long long ds[100001];
long long dt[100001];
long long du[100001];
long long dv[100001];
void dijkstra1(long long start=s)
{
    for(long long i=0;i<n;i++)
    {
        ds[i]=1000000000000000000;
    }
    ds[start]=0;
    set< pair<long long,long long> > st;
    st.insert({ds[start],start});
    while(!st.empty())
    {
        long long cur=st.begin()->second;
        st.erase(st.begin());
        for(auto p : adj[cur])
        {
            long long node=p.first;
            long long len=p.second;
            if(ds[cur]+len<ds[node])
            {
               st.erase({ds[node],node});
               ds[node]=ds[cur]+len;
               st.insert({ds[node],node});
            }
        }
    }
}
void dijkstra2(long long start=t)
{
    for(long long i=0;i<n;i++)
    {
        dt[i]=1000000000000000000;
    }
    dt[start]=0;
    set< pair<long long,long long> > st;
    st.insert({dt[start],start});
    while(!st.empty())
    {
        long long cur=st.begin()->second;
        st.erase(st.begin());
        for(auto p : adj[cur])
        {
            long long node=p.first;
            long long len=p.second;
            if(dt[cur]+len<dt[node])
            {
               st.erase({dt[node],node});
               dt[node]=dt[cur]+len;
               st.insert({dt[node],node});
            }
        }
    }
}
void dijkstra3(long long start=u)
{
    for(long long i=0;i<n;i++)
    {
        du[i]=1000000000000000000;
    }
    du[start]=0;
    set< pair<long long,long long> > st;
    st.insert({du[start],start});
    while(!st.empty())
    {
        long long cur=st.begin()->second;
        st.erase(st.begin());
        for(auto p : adj[cur])
        {
            long long node=p.first;
            long long len=p.second;
            if(du[cur]+len<du[node])
            {
               st.erase({du[node],node});
               du[node]=du[cur]+len;
               st.insert({du[node],node});
            }
        }
    }
}
void dijkstra4(long long start=v)
{
    for(long long i=0;i<n;i++)
    {
        dv[i]=1000000000000000000;
    }
    dv[start]=0;
    set< pair<long long,long long> > st;
    st.insert({dv[start],start});
    while(!st.empty())
    {
        long long cur=st.begin()->second;
        st.erase(st.begin());
        for(auto p : adj[cur])
        {
            long long node=p.first;
            long long len=p.second;
            if(dv[cur]+len<dv[node])
            {
               st.erase({dv[node],node});
               dv[node]=dv[cur]+len;
               st.insert({dv[node],node});
            }
        }
    }
}
long long f[100001];
long long rez=1000000000000000000;
long long dfs(long long cur,bool is)
{
    if(f[cur]==-1)
    {
        if(ds[cur]+dt[cur]==ds[t])
        {
            f[cur]=dv[cur];
            for(auto p : adj[cur])
            {
                long long node=p.first;
                long long len=p.second;
                if(is && ds[cur]+len==ds[node])
                {
                    f[cur]=min(f[cur],dfs(node,is));
                }
                else if(!is && dt[cur]+len==dt[node])
                {
                    f[cur]=min(f[cur],dfs(node,is));
                }
                rez=min(rez,du[cur]+f[cur]);
            }
        }
        else
        {
            f[cur]=1000000000000000000;
        }
    }
    return f[cur];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> s >> t >> u >> v;
    s--;
    t--;
    u--;
    v--;
    long long a,b,c;
    for(long long i=0;i<m;i++)
    {
        cin >> a >> b >> c;
        a--;
        b--;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    dijkstra1();
    dijkstra2();
    dijkstra3();
    dijkstra4();
    rez=du[v];
    memset(f,-1,8*n);
    dfs(s,1);
    memset(f,-1,8*n);
    dfs(t,0);
    cout << rez;
    return 0;
}

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