Submission #1309224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309224		liptonek	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	210 ms	15384 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;

const long long INF=1e18;

struct Edge
{
    int to, weight;
};

int n,m,s,t,u,v;

vector<vector<Edge>> adj;

void dijkstra(int start, vector<long long>& dist)
{
    fill(dist.begin(), dist.end(), INF);

    dist[start]=0;

    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;

    pq.push({0,start});

    while(!pq.empty())
    {
        long long d=pq.top().first;
        int u=pq.top().second;
        pq.pop();

        if(d>dist[u])
        {
            continue;
        }

        for(const auto& e : adj[u])
        {
            if(dist[u]+e.weight<dist[e.to])
            {
                dist[e.to]=dist[u]+e.weight;

                pq.push({dist[e.to], e.to});
            }
        }
    }
}

long long dag(const vector<long long>& ds, const vector<long long>& dt, const vector<long long>& du, const vector<long long>& dv)
{
    long long sp=ds[t];

    vector<int> nodes;

    for(int i=1; i<=n; i++)
    {
        if(ds[i]!=INF && dt[i]!=INF && ds[i]+dt[i]==sp)
        {
            nodes.push_back(i);
        }
    }

    sort(nodes.begin(), nodes.end(), [&](int a, int b)
    {
        return ds[a]<ds[b];
    });

    vector<long long> ndu(n+1,INF);

    long long current=INF;

    for(int u : nodes)
    {
        if(du[u]<ndu[u])
        {
            ndu[u]=du[u];
        }

        if(ndu[u]!=INF && dv[u]!=INF)
        {
            long long cost=ndu[u]+dv[u];

            if(cost<current)
            {
                current=cost;
            }
        }

        for(const auto& e : adj[u])
        {
            if(ds[u]+e.weight+dt[e.to]==sp)
            {
                int v=e.to;

                if(ndu[u]<ndu[v])
                {
                    ndu[v]=ndu[u];
                }
            }
        }
    }

    return current;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m>>s>>t>>u>>v;

    adj.resize(n+1);

    for(int i=0; i<m; i++)
    {
        int q,w,e;
        cin>>q>>w>>e;

        adj[q].push_back({w,e});
        adj[w].push_back({q,e});
    }

    vector<long long> ds(n+1);
    vector<long long> dt(n+1);
    vector<long long> du(n+1);
    vector<long long> dv(n+1);

    dijkstra(s,ds);
    dijkstra(t,dt);
    dijkstra(u,du);
    dijkstra(v,dv);

    long long ans=du[v];

    ans=min(ans, dag(ds,dt,du,dv));
    ans=min(ans,dag(ds,dt,dv,du));

    cout<<ans<<endl;

    return 0;
}

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