Submission #1115632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115632		staszic_ojuz	Commuter Pass (JOI18_commuter_pass)	C++17	15 / 100	159 ms	23092 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

using ll=long long;

const int MAX=1e5+7;

vector<pair<int, ll>> G[MAX];
bool odw[MAX];
int skad[MAX];

void usun(int v, int u){
    int akt=u;
    while (akt!=v){
        //cout << akt << " " << skad[akt] << endl;
        for (int i=0; i<(int)G[akt].size(); i++){
            if (G[akt][i].first == skad[akt]) G[akt][i].second = 0;
        }
        for (int i=0; i<(int)G[skad[akt]].size(); i++){
            if (G[skad[akt]][i].first == akt) G[skad[akt]][i].second = 0;
        }
        akt = skad[akt];
    }
}

ll dijkstra(int v, int u){
    priority_queue<pair<pair<ll, int>, int>> Q;
    Q.push({{0, v}, v});

    for (int i=0; i<MAX; i++) odw[i] = false;

    while (!Q.empty()){
        auto w=Q.top();
        Q.pop();
        //cout << w.first.first << " " << w.first.second << "skibidi " << w.second << endl;
        if (odw[w.first.second]) continue;
        odw[w.first.second] = true;
        skad[w.first.second] = w.second;

        if (w.first.second==u){
            usun(v, u);
            return -w.first.first;
        }

        for (auto k:G[w.first.second]){
            if (odw[k.first]) continue;
            Q.push({{w.first.first-k.second, k.first}, w.first.second});
        }
    }

    return -1e15;
}

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

    ll c;

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

    dijkstra(s, t);
    cout << dijkstra(u, v) << "\n";

    return 0;
}

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