제출 #729411

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
729411		Pring	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	7 ms	9724 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> pii;

const int MXN = 100005;
// int n, m, s, t, u, v, father[MXN], du[MXN], dv[MXN], uu = LLONG_MAX, vv = LLONG_MAX;
// int n, m, s, t, u, v, ds[MXN], du[MXN], dv[MXN], ans = LLONG_MAX, uu = LLONG_MAX, vv = LLONG_MAX;
// vector<pii> edge[MXN];
// vector<int> path, father[MXN];
// set<int> reach[MXN];
// bool B = false;
// bitset<MXN> b;

int n, m, s, t, u, v, du[MXN], dv[MXN], ds[MXN], ans = LLONG_MAX, dp[2][MXN];
vector<pii> edge[MXN];
vector<int> path, father[MXN];
bitset<MXN> b;

vector<int> R[MXN], L[MXN];

void GET_PATH() {
    b.reset();
    priority_queue<pair<int, pii>, vector<pair<int, pii>>, greater<pair<int, pii>>> pq;
    pq.push({0, {s, s}});
    while (pq.size()) {
        pair<int, pii> now = pq.top();
        pq.pop();
        if (b[now.second.second]) {
            if (ds[now.second.second] == now.first) father[now.second.second].push_back(now.second.first);
            continue;
        }
        b[now.second.second] = true;
        ds[now.second.second] = now.first;
        father[now.second.second].push_back(now.second.first);
        for (auto &i : edge[now.second.second]) {
            if (b[i.first]) continue;
            pq.push({now.first + i.second, {now.second.second, i.first}});
        }
    }
    b.reset();
    queue<int> q;
    q.push(t);
    while (q.size()) {
        int now = q.front();
        q.pop();
        if (b[now]) continue;
        b[now] = true;
        path.push_back(now);
        for (auto &i : father[now]) {
            if (i == now) continue;
            if (b[i]) continue;
            L[now].push_back(i);
            R[i].push_back(now);
            q.push(i);
        }
    }
}

void DIJKSTRA(int start, int *arr) {
    b.reset();
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    while (pq.size()) {
        pii now = pq.top();
        pq.pop();
        if (b[now.second]) continue;
        b[now.second] = true;
        arr[now.second] = now.first;
        for (auto &i : edge[now.second]) {
            if (b[i.first]) continue;
            pq.push({now.first + i.second, i.first});
        }
    }
}

// void GET_REACH(int id) {
//     queue<int> q;
//     q.push(id);
//     while (q.size()) {
//         int now = q.front();
//         q.pop();
//         // if (b[now]) {
//         //     continue;
//         // }
//         // b[now] = true;
//         if (!reach[id].insert(now).second) continue;
//         // path.push_back(now);
//         for (auto &i : father[now]) {
//             q.push(i);
//         }
//     }
// }

void BFS() {
    queue<int> q;
    q.push(s);
    while (q.size()) {
        int now = q.front();
        q.pop();
        dp[0][now] = LLONG_MAX;
        dp[1][now] = LLONG_MAX;
        for (auto &i : L[now]) {
            dp[0][now] = min(dp[0][now], dp[0][i]);
            dp[1][now] = min(dp[1][now], dp[1][i]);
        }
        dp[0][now] = min(dp[0][now], du[now]);
        dp[1][now] = min(dp[1][now], dv[now]);
        ans = min(ans, min(dp[0][now] + dv[now], dp[1][now] + du[now]));
        for (auto &i : R[now]) q.push(i);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int x, y, z;
    cin >> n >> m >> s >> t >> u >> v;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> z;
        edge[x].push_back({y, z});
        edge[y].push_back({x, z});
    }
    GET_PATH();
    DIJKSTRA(u, du);
    DIJKSTRA(v, dv);
    // for (int i = 1; i <= n; i++) {
    //     cout << R[i].size() << ' ';
    //     for (auto &j : R[i]) cout << j << ' ';
    //     cout << endl;
    // }
    // cout << endl;
    // for (int i = 1; i <= n; i++) {
    //     cout << L[i].size() << ' ';
    //     for (auto &j : L[i]) cout << j << ' ';
    //     cout << endl;
    // }
    ans = du[v];
    BFS();
    cout << ans << endl;
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67