Submission #335506

#	Time	Username	Problem	Language	Result	Execution time	Memory
335506		alien_lover	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	413 ms	20264 KiB

commuter_pass

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <algorithm>

using namespace std;

typedef long long ll;

#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()

const int PRIME = 1e9 + 7;
const int MX = 100000;

int n, m, s, t, u, v;
vector<pair<int, int>> adjList[MX];
ll distFromU[MX], distFromV[MX], dpU[MX], dpV[MX], dist[MX];

void doDijkstra(int source, ll arr[]){
    // vector<ll> dist(n, LLONG_MAX);
    fill(arr, arr + MX, LLONG_MAX / 3);
    arr[source] = 0;

    using DistNode = pair<ll, int>;
    priority_queue<DistNode, vector<DistNode>, greater<DistNode>> pq;
    pq.push({0, source});

    while(!pq.empty()){
        int currNode = pq.top().second;
        if(arr[currNode] < pq.top().first){
            pq.pop();
            continue;
        }
        pq.pop();

        for(auto edge: adjList[currNode]){
            if(arr[currNode] + edge.second < arr[edge.first]){
                pq.push({arr[edge.first] = arr[currNode] + edge.second, edge.first});
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    s--; t--; u--; v--;

    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        adjList[a].push_back({b, c});
        adjList[b].push_back({a, c});
    }

    doDijkstra(u, distFromU);
    doDijkstra(v, distFromV);

    // vector<ll> distFromU = doDijkstra(u);
    // vector<ll> distFromV = doDijkstra(v);

    // vector<ll> dpU(n, LLONG_MAX / 3);
    // vector<ll> dpV(n, LLONG_MAX / 3);
    fill(dpU, dpU + MX, LLONG_MAX / 3);
    fill(dpV, dpV + MX, LLONG_MAX / 3);
    fill(dist, dist + MX, LLONG_MAX / 3);
    // vector<ll> dist(n, LLONG_MAX / 3);

    dist[s] = 0;
    dpU[s] = distFromU[s];
    dpV[s] = distFromV[s];

    using DistNodeSrc = pair<ll, pair<int, int>>;
    priority_queue<DistNodeSrc, vector<DistNodeSrc>, greater<DistNodeSrc>> pq;
    pq.push({0, {s, s}});

    while(!pq.empty()){
        int currNode = pq.top().second.first;
        int parent = pq.top().second.second;
        if(dist[currNode] < pq.top().first){
            pq.pop();
            continue;
        }
        pq.pop();

        // cout << currNode + 1 << "CURR " << parent + 1 << '\n';
        // cout << distFromU[currNode] << "dfU " << dpU[parent] << '\n';
        // cout << distFromV[currNode] << "dfV " << dpV[parent] << '\n';
        // cout << endl;

        if(min(distFromU[currNode], dpU[parent]) + min(distFromV[currNode], dpV[parent]) <= 
    dpU[currNode] + dpV[currNode]){
            dpU[currNode] = min(distFromU[currNode], dpU[parent]);
            dpV[currNode] = min(distFromV[currNode], dpV[parent]); 
        }

        // if(dist[currNode] == pq.top().first){
        //     if(min(distFromU[currNode], dpU[parent]) + min(distFromV[currNode], dpV[parent]) <= dpU[currNode] + dpV[currNode])
        //     {
        //         dpU[currNode] = min(distFromU[currNode], dpU[parent]);
        //         dpV[currNode] = min(distFromV[currNode], dpV[parent]); 
        //     }
        // }else{
        //     dpU[currNode] = min(distFromU[currNode], dpU[parent]);
        //     dpV[currNode] = min(distFromV[currNode], dpV[parent]);
        // }

        for(auto edge: adjList[currNode]){
            if(dist[currNode] + edge.second < dist[edge.first]){
                // cout << "WUB";
                dpU[edge.first] = LLONG_MAX / 3;
                dpV[edge.first] = LLONG_MAX / 3;
                pq.push({dist[edge.first] = dist[currNode] + edge.second, {edge.first, currNode}});
            }else if(dist[currNode] + edge.second == dist[edge.first]){
                if(min(distFromU[edge.first], dpU[currNode]) + min(distFromV[edge.first], dpV[currNode]) <= 
            dpU[edge.first] + dpV[edge.first]){
                    dpU[edge.first] = min(distFromU[edge.first], dpU[currNode]);
                    dpV[edge.first] = min(distFromV[edge.first], dpV[currNode]); 
                }
            }
        }
    }
    ll ans = min(distFromU[v], dpU[t] + dpV[t]);

    fill(dpU, dpU + MX, LLONG_MAX / 3);
    fill(dpV, dpV + MX, LLONG_MAX / 3);
    fill(dist, dist + MX, LLONG_MAX / 3);
    // for(int i = 0; i < n; i++){
    //     cerr << dpU[i] << ' ' << dpV[i] << '\n';
    // }

    dist[t] = 0;
    dpU[t] = distFromU[t];
    dpV[t] = distFromV[t];
    pq.push({0, {t, t}});
    
    while(!pq.empty()){
        int currNode = pq.top().second.first;
        int parent = pq.top().second.second;
        if(dist[currNode] < pq.top().first){
            pq.pop();
            continue;
        }
        pq.pop();

        if(min(distFromU[currNode], dpU[parent]) + min(distFromV[currNode], dpV[parent]) <= 
        dpU[currNode] + dpV[currNode]){
            dpU[currNode] = min(distFromU[currNode], dpU[parent]);
            dpV[currNode] = min(distFromV[currNode], dpV[parent]); 
        }

        for(auto edge: adjList[currNode]){
            if(dist[currNode] + edge.second < dist[edge.first]){
                // cout << "WUB";
                dpU[edge.first] = LLONG_MAX / 3;
                dpV[edge.first] = LLONG_MAX / 3;
                pq.push({dist[edge.first] = dist[currNode] + edge.second, {edge.first, currNode}});
            }else if(dist[currNode] + edge.second == dist[edge.first]){
                if(min(distFromU[edge.first], dpU[currNode]) + min(distFromV[edge.first], dpV[currNode]) <= 
            dpU[edge.first] + dpV[edge.first]){
                    dpU[edge.first] = min(distFromU[edge.first], dpU[currNode]);
                    dpV[edge.first] = min(distFromV[edge.first], dpV[currNode]); 
                }
            }
        }
    }

    // ll ans = distFromU[v];
    

    // for(int i = 0; i < n; i++){
    //     if(distS[i] + distFromT[i] == distS[t]){
    //         ans = min(ans, dp[i]);
    //     }
    //     // cout << el << '\n';
    // }
    cout << min(ans, dpU[s] + dpV[s]) << '\n';
    // cout << ans << '\n';
}

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