Submission #703068

#	Time	Username	Problem	Language	Result	Execution time	Memory
703068		speedyArda	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	503 ms	27260 KiB

commuter_pass

#include "bits/stdc++.h"

using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
const ll INF = 1e18;
bool visited[MAXN];
ll dpU[MAXN], dpV[MAXN], dp[2][MAXN], dpS[MAXN], ans = 2e18;
//int par[MAXN];
vector< vector< pair<long long, long long > > > adj(MAXN);

void dijkstra1(int v, ll arr[])
{
    fill(visited, visited + MAXN, false);
    priority_queue< pair<ll, ll > > pq;
    pq.push({0LL, v});
    while(!pq.empty())
    {
        pair<ll, ll> curr = pq.top();   
        pq.pop();
        if(!visited[curr.second])
        {
            arr[curr.second] = -curr.first;
            visited[curr.second] = true;
            for(pair<ll, ll>  e : adj[curr.second])
                pq.push({curr.first - e.first, e.second});
        }
    }
}

void dijkstra2(int start, int end)
{
    fill(dp[0], dp[0] + MAXN,  INF);
    fill(dp[1], dp[1] + MAXN, INF);
    fill(visited, visited + MAXN, false);
    priority_queue< pair<ll, pair<ll, ll> > > pq;
    pq.push({0, {start, 0}});
    dp[0][0] = dp[1][0] = INF;
    while(!pq.empty())
    {
        pair<ll, pair<ll, ll> > curr = pq.top();
        pq.pop();
        ll node = curr.second.first;
        ll dist = curr.first;
        ll par = curr.second.second;
        if(!visited[node])
        {
            dpS[node] = -dist;
            visited[node] = true;
            dp[0][node] = min(dp[0][par], dpU[node]);
            dp[1][node] = min(dp[1][par], dpV[node]);
            for(pair<ll, ll> e : adj[node])
            {
                pq.push({dist - e.first, {e.second, node}});
            }
        } else if(dpS[node] == -dist)
        {
            if(min(dpU[node], dp[0][par]) + min(dpV[node], dp[1][par]) <= dp[0][node] + dp[1][node]) {
                dp[0][node] = min(dp[0][par], dpU[node]);
                dp[1][node] = min(dp[1][par], dpV[node]);
            }
        }

    }

    ans = min(ans, dp[0][end] + dp[1][end]);
}

int main() 
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        adj[a].push_back({c, b});
        adj[b].push_back({c, a});
    }
    
    dijkstra1(u, dpU);
    dijkstra1(v, dpV);

    ans = dpU[v];
    
    dijkstra2(s, t);
    dijkstra2(t, s);

    cout << ans << "\n";
}

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