Submission #930316

#	Time	Username	Problem	Language	Result	Execution time	Memory
930316		Lukap	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	643 ms	44368 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 500;
const ll INF = 1e16;

int n, m;
int s,t,u,v;
vector<pair<int, ll> > susjedi[MAXN], parent[MAXN], dag[MAXN];
int bio[MAXN], bio2[MAXN];
queue<int> q;
ll distu[MAXN], distv[MAXN], dists[MAXN];
pair<ll, ll> dp[MAXN];
ll rj = INF;

set<pair<ll, ll> > sett;

void bfs (int x) {
    for(int i = 0; i < n; i++){
        if(i == s){
            sett.insert(make_pair(0,s));
            dists[s] = 0;
            continue;
        }
        sett.insert(make_pair(INF,i));
        dists[i] = INF;
    }

    while(!sett.empty()){
        int x = (*sett.begin()).second;
        sett.erase(sett.begin());

        for (auto it: susjedi[x]) {
            int nx = it.first;
            if (dists[nx] > dists[x] + it.second) {
                sett.erase({dists[nx], nx});
                dists[nx] = dists[x] + it.second;
                sett.insert ({dists[nx], nx});
                parent[nx].clear ();
                parent[nx].push_back ({x, it.second});
            }
            else if (dists[nx] == dists[x] + it.second) {
                parent[nx].push_back ({x, it.second});
            }
        }
    }
}

void dfs (int x) {
    bio[x] = -2;
    for (auto nx: parent[x]) {
        dag[nx.first].push_back({x, nx.second});
        if (bio[nx.first] != -2) dfs (nx.first);
    }
}

void dijkstra(){
    for(int i = 0; i < n; i++){
        if(i == u){
            sett.insert(make_pair(0,u));
            distu[u] = 0;
            continue;
        }
        sett.insert(make_pair(INF,i));
        distu[i] = INF;
    }

    while(!sett.empty()){
        int x = (*sett.begin()).second;
        sett.erase(sett.begin());

        for (auto it: susjedi[x]) {
            int nx = it.first;
            if (distu[nx] > distu[x] + it.second) {
                sett.erase({distu[nx], nx});
                distu[nx] = distu[x] + it.second;
                sett.insert ({distu[nx], nx});
            }
        }
    }

    sett.clear ();
    for(int i = 0; i < n; i++){
        if(i == v){
            sett.insert(make_pair(0,v));
            distv[v] = 0;
            continue;
        }
        sett.insert(make_pair(INF,i));
        distv[i] = INF;
    }

    while(!sett.empty()){
        int x = (*sett.begin()).second;
        sett.erase(sett.begin());

        for (auto it: susjedi[x]) {
            int nx = it.first;
            if (distv[nx] > distv[x] + it.second) {
                sett.erase({distv[nx], nx});
                distv[nx] = distv[x] + it.second;
                sett.insert ({distv[nx], nx});
            }
        }
    }
}


void solve () {
    dijkstra ();
    for (int i = 0; i < n; i++) {
        if (bio[i] != -2) continue;
        dp[i].first = distu[i];
        dp[i].second = distv[i];
    }
    rj = distu[v];

    memset (bio2, -1, sizeof (bio2));
    q.push (s);
    bio2[s] = 0;
    while (!q.empty ()) {
        int x = q.front ();
        q.pop ();
        for (auto nx: dag[x]) {
            dp[nx.first].first = min (dp[nx.first].first, dp[x].first);
//            cout << "AAAAAA " << x << ' ' << nx.first << ' ' << dp[nx.first].first << ' ' << dp[nx.first].second << "\n";
            if (bio2[nx.first] == -1) {
                bio2[nx.first] = bio2[x] + 1;
                q.push (nx.first);
            }
        }
    }
    memset (bio2, -1, sizeof (bio2));
    q.push (t);
    bio2[t] = 0;
    while (!q.empty ()) {
        int x = q.front ();
        q.pop ();
        for (auto nx: parent[x]) {
            dp[nx.first].second = min (dp[nx.first].second, dp[x].second);
//            cout << "AAAAAAAAAAAA" << ' ' << x << ' ' << dp[x].second << ' ' << nx.first << ' ' << dp[nx.first].second << "\n";
            if (bio2[nx.first] == -1) {
                bio2[nx.first] = bio2[x] + 1;
                q.push (nx.first);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (bio[i] != -2) continue;
        rj = min (rj, dp[i].first + dp[i].second);
        dp[i].first = distu[i];
        dp[i].second = distv[i];
    }

    memset (bio2, -1, sizeof (bio2));
    q.push (s);
    bio2[s] = 0;
    while (!q.empty ()) {
        int x = q.front ();
        q.pop ();
        for (auto nx: dag[x]) {
            dp[nx.first].second = min (dp[nx.first].second, dp[x].second);
//            cout << "AAAAAA " << x << ' ' << nx.first << ' ' << dp[nx.first].first << ' ' << dp[nx.first].second << "\n";
            if (bio2[nx.first] == -1) {
                bio2[nx.first] = bio2[x] + 1;
                q.push (nx.first);
            }
        }
    }
    memset (bio2, -1, sizeof (bio2));
    q.push (t);
    bio2[t] = 0;
    while (!q.empty ()) {
        int x = q.front ();
        q.pop ();
        for (auto nx: parent[x]) {
            dp[nx.first].first = min (dp[nx.first].first, dp[x].first);
//            cout << "AAAAAAAAAAAA" << ' ' << x << ' ' << dp[x].second << ' ' << nx.first << ' ' << dp[nx.first].second << "\n";
            if (bio2[nx.first] == -1) {
                bio2[nx.first] = bio2[x] + 1;
                q.push (nx.first);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        if (bio[i] != -2) continue;
        rj = min (rj, dp[i].first + dp[i].second);
    }
}

int main () {
    ios_base::sync_with_stdio (false);
    cin.tie (0);
    memset (bio, -1, sizeof (bio));

    cin >> n >> m >> s >> t >> u >> v;
    s--;t--;u--;v--;

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



    bfs (s);
    dfs (t);

    solve ();


    cout << rj;

    return 0;
}

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