Submission #753782

#	Time	Username	Problem	Language	Result	Execution time	Memory
753782		buihuynhtay	Commuter Pass (JOI18_commuter_pass)	C++14	15 / 100	923 ms	262144 KiB

commuter_pass

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

#define Size(x) ((int)(x).size())
#define MASK(i) (1LL<<(i))
#define bit(mask, i) (((mask) >> (i)) & 1)

const long long inf = 1e18 + 7;
const int mod = 1e9 + 7;
const int N = 1e5 + 1;

template<class T1, class T2>
    bool Min(T1 &a, T2 b){
        if(a >= b){ a = b; return true;}
        return false;
    }

int n, m, s, t, u, v;
bool vs[N];
long long minDist[N], minDistU[N], minDistV[N], dpU[N], dpV[N];
vector<pair<int,int>> graph[N];

#define pli pair<long long, int>
void dijkstra(int s, long long minDist[]){
    for(int i = 1; i <= n; i++) minDist[i] = inf;
    minDist[s] = 0;
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    pq.push({minDist[s], s});
    while(pq.empty() == 0){
        long long du = pq.top().first;
        int u = pq.top().second;
        pq.pop();
        if(du != minDist[u]) continue;

        for(pair<int,int> child : graph[u]){
            int v = child.first, w = child.second;
            if(Min(minDist[v], minDist[u] + w)){
                pq.push({minDist[v], v});
            }
        }
    }
}

void solve(){
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    dijkstra(u, minDistU);
    dijkstra(v, minDistV);

    for(int i = 1; i <= n; i++) minDist[i] = inf;
    minDist[s] = 0;
    for(int i = 0; i <= n; i++){
        dpU[i] = dpV[i] = inf;
    }

    #define plii pair<long long, pair<int, int>>
    priority_queue<plii, vector<plii>, greater<plii>> pq;
    pq.push({minDist[s], {s, 0}});

    while(pq.empty() == 0){
        long long du = pq.top().first;
        int u = pq.top().second.first;
        int par = pq.top().second.second;
        pq.pop();
        if(du != minDist[u]) continue;
        if(min(minDistU[u], dpU[par]) + min(minDistV[u], dpV[par])
           < dpU[u] + dpV[u]){
            dpU[u] = min(minDistU[u], dpU[par]);
            dpV[u] = min(minDistV[u], dpV[par]);
        }
        if(!vs[u]){
            vs[u] = true;
            for(pair<int,int> child : graph[u]){
                int v = child.first, w = child.second;
                if(Min(minDist[v], minDist[u] + w)){
                    pq.push({minDist[v], {v, u}});
                }
            }
        }
    }
    cout << min(dpU[t] + dpV[t], minDistU[v]) << '\n';
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

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