Submission #1008957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1008957		makanhulia	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	151 ms	23496 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int ukr = 2e5+10;
ll dp[ukr];
ll bf[ukr];
ll n, m, s, t, u, v, a, b, c, id;
struct babi{
    ll id, x, par;
    bool operator < (const babi &other) const{
        return id > other.id;
    }
};
vector<vector<pair<ll,ll>>> adj(ukr);
vector<ll> vc;
priority_queue<babi> pq;
void solve(){
    cin >> n >> m >> s >> t >> u >> v;
    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    for(int i = 0; i <= n; i++){
        sort(adj[i].begin(), adj[i].end());
        dp[i] = 1e18;
    }
    dp[s] = 0;
    pq.push({0, s, -1});
    while(!pq.empty()){
        babi rn = pq.top();
        pq.pop();
        if(!bf[rn.x]){
            bf[rn.x] = rn.par;
            for(auto i : adj[rn.x]){
                if(dp[i.first] > dp[rn.x] + i.second){
                    dp[i.first] = dp[rn.x] + i.second;
                    pq.push({dp[i.first], i.first, rn.x});
                }
            }
        }
    }
    ll kcau = t;
    while(kcau != -1){
        vc.push_back(kcau);
        kcau = bf[kcau];
    }
    id = vc.size();
    for(int i = 0; i < id-1; i++){
        ll l = 0, r = adj[vc[i]].size()-1;
        while(l <= r){
            ll mid = l + (r-l)/2;
            if(adj[vc[i]][mid].first == vc[i+1]){
                adj[vc[i]][mid].second = 0;
                break;
            }
            if(adj[vc[i]][mid].first <= vc[i+1]){
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
        l = 0, r = adj[vc[i+1]].size()-1;
        while(l <= r){
            ll mid = l + (r-l)/2;
            if(adj[vc[i+1]][mid].first == vc[i]){
                adj[vc[i+1]][mid].second = 0;
                break;
            }
            if(adj[vc[i+1]][mid].first <= vc[i]){
                l = mid+1;
            }else{
                r = mid-1;
            }
        }
    }
    for(int i = 0; i <= n; i++){
        dp[i] = 1e18; bf[i] = 0;
    }
    pq.push({0, u, -1});
    dp[u] = 0;
    while(!pq.empty()){
        babi rn = pq.top();
        pq.pop();
        if(!bf[rn.x]){
            bf[rn.x] = rn.par;
            for(auto i : adj[rn.x]){
                if(dp[i.first] > dp[rn.x] + i.second){
                    dp[i.first] = dp[rn.x] + i.second;
                    pq.push({dp[i.first], i.first, rn.x});
                }
            }
        }
    }
    /* vc.clear();
    kcau = v;
    while(kcau != -1){
        vc.push_back(kcau);
        kcau = bf[kcau];
    }
    for(auto i : vc){
        cout << i << " ";
    } */
    cout << "\n";
    cout << dp[v] << "\n";
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
}

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