Submission #110080

#	Time	Username	Problem	Language	Result	Execution time	Memory
110080		popovicirobert	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	902 ms	24392 KiB

commuter_pass

#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const ll INF = 1e18;

vector < vector < pair <int, int> > > g;
vector <ll> dst[4];
int n;

inline void dijkstra(int nod, vector <ll> &dst) {

    dst.resize(n + 1);
    fill(dst.begin(), dst.end(), INF);

    priority_queue < pair <ll, int> > pq;
    pq.push({0, nod});
    dst[nod] = 0;

    vector <bool> vis(n + 1);
    fill(vis.begin(), vis.end(), 0);

    while(pq.size()) {
        pair <ll, int> cur = pq.top();
        pq.pop();

        if(vis[cur.second]) {
            continue;
        }

        vis[cur.second] = 1;

        for(auto it : g[cur.second]) {
            if(dst[it.first] > -cur.first + it.second) {
                dst[it.first] = -cur.first + it.second;
                pq.push({-dst[it.first], it.first});
            }
        }

    }

}

vector <bool> vis;
vector <int> top;

void dfs(int nod, vector < vector <int> > &dag) {
    vis[nod] = 1;

    for(auto it : dag[nod]) {
        if(vis[it] == 0) {
            dfs(it, dag);
        }
    }

    top.push_back(nod);
}


int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, m, s, t, u, v;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

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

    g.resize(n + 1);

    for(i = 1; i <= m; i++) {
        int x, y, c;
        cin >> x >> y >> c;
        g[x].push_back({y, c});
        g[y].push_back({x, c});
    }

    vis.resize(n + 1);

    ll ans = INF;

    for(int p = 0; p < 2; p++) {
        swap(u, v);

        dijkstra(s, dst[0]); // s
        dijkstra(t, dst[1]); // t
        dijkstra(u, dst[2]); // u
        dijkstra(v, dst[3]); // v

        ans = min(ans, dst[2][v]);

        vector < vector <int> > dag(n + 1);

        for(i = 1; i <= n; i++) {
            for(auto it : g[i]) {
                if(dst[0][it.first] + it.second + dst[1][i] == dst[0][t]) {
                    dag[it.first].push_back(i);
                }
            }
        }

        fill(vis.begin(), vis.end(), 0);
        top.clear();

        for(i = 1; i <= n; i++) {
            if(vis[i] == 0 && dst[0][i] + dst[1][i] == dst[0][t]) {
                dfs(i, dag);
            }
        }

        vector <ll> dp(n + 1, INF);
        for(auto nod : top) {

            dp[nod] = min(dp[nod], dst[3][nod]);

            for(auto it : dag[nod]) {
                dp[nod] = min(dp[nod], dp[it]);
            }

            ans = min(ans, dp[nod] + dst[2][nod]);

        }

    }

    cout << ans;

    //cin.close();
    //cout.close();
    return 0;
}

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