Submission #1185746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185746		attky	Commuter Pass (JOI18_commuter_pass)	C++20	0 / 100	157 ms	25172 KiB

commuter_pass

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct Vertice {
    int end, weight;
};

struct compare {
    bool operator() (Vertice a, Vertice b) {
        return a.weight < b.weight;
    }
};

vector<Vertice> graph[100001];
vector<int> before[100001];
vector<int> inverseBefore[100001];
int distMin[100001], distMinU[100001], distMinV[100001], mini = 1e18;
bool vu[100001], vu2[100001];

void dfs1(int pos) {
    vu[pos] = true;
    for(int loop = 0; loop < before[pos].size(); ++loop) {
        if(!vu[before[pos][loop]]) {
            dfs1(before[pos][loop]);
        }
        distMinU[pos] = min(distMinU[pos], distMinU[before[pos][loop]]);
    }
}

void dfs2(int pos) {
    vu2[pos] = true;
    for(int loop = 0; loop < inverseBefore[pos].size(); ++loop) {
        if(vu[inverseBefore[pos][loop]]) {
            if(!vu2[inverseBefore[pos][loop]]) {
                dfs2(inverseBefore[pos][loop]);
            }
            distMinU[pos] = min(distMinU[pos], distMinU[inverseBefore[pos][loop]]);
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, s, t, u, v;
    cin >> n >> m >> s >> t >> u >> v;
    s--;t--;u--;v--;
    for(int loop = 0; loop < m; ++loop) {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a-1].push_back({b-1, c});
        graph[b-1].push_back({a-1, c});
    }
    for(int loop = 0; loop < n; ++loop) {
        distMin[loop] = 1e18;
        distMinU[loop] = 1e18;
        distMinV[loop] = 1e18;
    }

    priority_queue<Vertice, vector<Vertice>, compare> q;
    
    q.push({s, 0});
    for(int loop = 0; loop < n; ++loop) {
        vu[loop] = false;
    }
    while(q.size() > 0) {
        Vertice enCours = q.top();
        q.pop();
        if(vu[enCours.end]) {
            continue;
        }
        vu[enCours.end] = true;
        for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
            if(distMin[graph[enCours.end][loop].end] > enCours.weight + graph[enCours.end][loop].weight) {
                q.push({graph[enCours.end][loop].end, graph[enCours.end][loop].weight + enCours.weight});
                before[graph[enCours.end][loop].end].clear();
                before[graph[enCours.end][loop].end].push_back(enCours.end);
                distMin[graph[enCours.end][loop].end] = enCours.weight + graph[enCours.end][loop].weight;
            }
            else if(distMin[graph[enCours.end][loop].end] == enCours.weight + graph[enCours.end][loop].weight) {
                before[graph[enCours.end][loop].end].push_back(enCours.end);
            }
        }
    }

    q.push({u, 0});
    for(int loop = 0; loop < n; ++loop) {
        vu[loop] = false;
    }
    while(q.size() > 0) {
        Vertice enCours = q.top();
        q.pop();
        if(vu[enCours.end]) {
            continue;
        }
        vu[enCours.end] = true;
        for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
            if(distMinU[graph[enCours.end][loop].end] > enCours.weight + graph[enCours.end][loop].weight) {
                q.push({graph[enCours.end][loop].end, enCours.weight + graph[enCours.end][loop].weight});
                distMinU[graph[enCours.end][loop].end] = enCours.weight + graph[enCours.end][loop].weight;
            }
        }
    }

    q.push({v, 0});
    for(int loop = 0; loop < n; ++loop) {
        vu[loop] = false;
    }
    while(q.size() > 0) {
        Vertice enCours = q.top();
        q.pop();
        if(vu[enCours.end]) {
            continue;
        }
        vu[enCours.end] = true;
        for(int loop = 0; loop < graph[enCours.end].size(); ++loop) {
            if(distMinV[graph[enCours.end][loop].end] > enCours.weight + graph[enCours.end][loop].weight) {
                q.push({graph[enCours.end][loop].end, enCours.weight + graph[enCours.end][loop].weight});
                distMinV[graph[enCours.end][loop].end] = enCours.weight + graph[enCours.end][loop].weight;
            }
        }
    }

    for(int loop = 0; loop < n; ++loop) {
        for(int looping = 0; looping < before[loop].size(); ++looping) {
            inverseBefore[before[loop][looping]].push_back(loop);
        }
    }

    for(int loop = 0; loop < n; ++loop) {
        vu[loop] = false;
    }
    dfs1(t);

    for(int loop = 0; loop < n; ++loop) {
        vu2[loop] = false;
    }
    dfs2(s);

    for(int loop = 0; loop < n; ++loop) {
        mini = min(mini, distMinU[loop] + distMinV[loop]);
    }
    cout << mini << '\n';
}

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