Submission #335468

#	Time	Username	Problem	Language	Result	Execution time	Memory
335468		alien_lover	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	394 ms	19944 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;

int n, m, s, t, u, v;
vector<pair<int, int>> adjList[100000];

vector<ll> doDijkstra(int source){
    vector<ll> dist(n, LLONG_MAX);
    dist[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(dist[currNode] < pq.top().first){
            pq.pop();
            continue;
        }
        pq.pop();

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    // freopen("TASK_NAME.in", "r", stdin);
    // freopen("TASK_NAME.out", "w", stdout);
    // Use scanf printf

    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});
    }

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

    // for(ll el: distFromV){
    //     cerr << el << '\n';
    // }
    
    vector<ll> dpU(n, LLONG_MAX);
    vector<ll> dpV(n, LLONG_MAX);
    vector<ll> dist(n, LLONG_MAX);

    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;
        if(dist[currNode] < pq.top().first){
            pq.pop();
            continue;
        }
        int parent = pq.top().second.second;
        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;

        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]){
                pq.push({dist[edge.first] = dist[currNode] + edge.second, {edge.first, currNode}});
            }
        }
    }
    ll ans = min(distFromU[v], dpU[t] + dpV[t]);

    fill(all(dist), LLONG_MAX);
    fill(all(dpU), LLONG_MAX);
    fill(all(dpV), LLONG_MAX);
    // 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;
        if(dist[currNode] < pq.top().first){
            pq.pop();
            continue;
        }
        int parent = pq.top().second.second;
        pq.pop();
        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]){
                pq.push({dist[edge.first] = dist[currNode] + edge.second, {edge.first, 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';
}

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