제출 #591036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591036		piOOE	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	872 ms	33524 KiB

commuter_pass

//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

//randoms
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

#define ll long long
#define trace(x) cout << #x << " = " << (x) << endl;
#define all(x) x.begin(), (x).end()
#define rall(x) x.rbegin(), (x).rend()
#define unique(x) x.erase(unique(all(x)), (x).end())
#define ld long double
#define sz(s) (int) size(s)

const int N = 100001;
const ll infL = 1e18;
const int infI = 1e9 + 7;
const ll mod = 998244353;

ll dist[4][N]; //s, t, u, v

vector<pair<int, ll>> g[N];
vector<int> gr[N], tops;
bool VisT[N], used[N];

ll minU[N], minV[N];

void dfs(int v) {
    used[v] = true;
    for (int to : gr[v]) {
        if (!used[to])
            dfs(to);
    }
    tops.push_back(v);
}

int s, t, u, v, n;


void calcDist(int i) {
    for (int j = 0; j < n; ++j)
        dist[i][j] = infL;
    if (i == 0) dist[i][s] = 0;
    else if (i == 1) dist[i][t] = 0;
    else if (i == 2) dist[i][u] = 0;
    else dist[i][v] = 0;
    set<pair<ll, int>> st;
    for (int j = 0; j < n; ++j)
        st.insert({dist[i][j], j});
    while (!st.empty()) {
        auto[w, V] = *st.begin();
        st.erase(st.begin());
        for (auto[to, W] : g[V]) {
            ll val = W + w;
            if (val < dist[i][to]) {
                st.erase({dist[i][to], to});
                dist[i][to] = val;
                st.insert({dist[i][to], to});
            }
        }
    }
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int m;
    cin >> n >> m >> s >> t >> u >> v;
    --s, --t, --u, --v;
    for (int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        --a, --b;
        g[a].emplace_back(b, w);
        g[b].emplace_back(a, w);
    }
    for (int i = 0; i < 4; ++i)
        calcDist(i);
    for (int i = 0; i < n; ++i) {
        for (auto[to, W] : g[i]) {
            if (dist[0][i] + W == dist[0][to]) {
                gr[i].push_back(to);
            }
        }
    }
    for (int i = 0; i < n; ++i)
        minU[i] = minV[i] = infL;
    for (int i = 0; i < n; ++i) {
        if (!used[i])
            dfs(i);
    }
    ll ans = dist[2][v];
    for (int x : tops) {
        if (x == t) VisT[x] = true;
        for (int to : gr[x]) {
            if (VisT[to]) {
                VisT[x] = true;
                minU[x] = min(minU[x], minU[to]);
                minV[x] = min(minV[x], minV[to]);
            }
        }
        if (VisT[x]) {
            ans = min({ans, minU[x] + dist[3][x], minV[x] + dist[2][x]});
            minU[x] = min(minU[x], dist[2][x]);
            minV[x] = min(minV[x], dist[3][x]);
        }
    }
    cout << ans;
    return 0;
}

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