Submission #1319263

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319263		ninstroyer	Commuter Pass (JOI18_commuter_pass)	C++20	31 / 100	289 ms	20236 KiB

commuter_pass

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

const ll nx = 1e5+5, inf = 4e18;

ll n,m,s,t,x,y,res=inf,mns[nx],mnt[nx],mnx[nx],mny[nx],vs[nx],dp[nx][2];
vector<pair<int,ll>> adj[nx];

void dijkstra(int st, ll mn[])
{
    mn[st] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0,st});
    while(!pq.empty())
    {
        auto [d, u] = pq.top();
        pq.pop();
        if(d > mn[u]) continue;
        for(auto [v,w] : adj[u])
        {
            if(d+w < mn[v])
            {
                mn[v] = d+w;
                pq.push({mn[v],v});
            }
        }
    }
}

void dfs(int u)
{
    if(vs[u]) return;
    vs[u] = 1; 
    dp[u][0] = inf;
    dp[u][1] = inf;
    for(auto [v, w] : adj[u])
    {
        if(mns[v] + mnt[v] > mns[t] || mns[v] < mns[u]) continue;
        dfs(v);
        dp[u][0] = min(dp[u][0],dp[v][0]);
        dp[u][1] = min(dp[u][1],dp[v][1]);
    }
    dp[u][0] = min(dp[u][0], mnx[u]);
    dp[u][1] = min(dp[u][1], mny[u]);
    res = min({res,dp[u][0]+dp[u][1]});
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>m>>s>>t>>x>>y;
    for(int i = 1; i <= n; i++) mns[i] = mnt[i] = mnx[i] = mny[i] = inf;
    for(int i = 1; i <= m; i++)
    {
        int u,v,w; cin>>u>>v>>w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dijkstra(s, mns);
    dijkstra(t, mnt);
    dijkstra(x, mnx);
    dijkstra(y, mny);
    dfs(s);
    cout<<min(res,mnx[y]);
}

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