제출 #1116538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1116538		staszic_ojuz	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	272 ms	24056 KiB

commuter_pass

#include<bits/stdc++.h>
#ifdef _DEBUG
#define ls(x) << x << ", "
#define lv(x) << #x << ": " << flush << x << ", "
#define pr(x) cout << "Line: " << __LINE__ << ", " x << endl;
#else
#define ls(x)
#define lv(x)
#define pr(x) ;
#endif
using namespace std;
typedef unsigned int uint;
typedef unsigned long long ull;

struct Edge {
    uint to;
    ull cost;
    Edge() {}
    Edge(uint to, ull cost) : to(to), cost(cost) {}
};

struct Vert {
    uint i;
    ull cost;
    Vert() {};
    Vert(uint i, ull cost) : i(i), cost(cost) {};
};

bool operator>(const Vert& a, const Vert& b) {
    return a.cost > b.cost;
}
constexpr ull ll_inf = 1e14;

void djikstra(uint r, uint n, const vector<vector<Edge>>& g,
    vector<uint> &orig, vector<ull>& cost) {
    orig.resize(n);
    cost.resize(n);
    fill(cost.begin(), cost.end(), ll_inf);
    fill(orig.begin(), orig.end(), n);
    priority_queue<Vert, vector<Vert>, greater<Vert>> q;
    q.push(Vert(r, 0));
    cost[r] = 0;
    orig[r] = 0;
    while (!q.empty()) {
        Vert vv = q.top();
        uint v = vv.i;
        pr(ls("visit") lv(v) lv(vv.cost) lv(cost[v]))
        q.pop();
        if (cost[v] < vv.cost) {
            // better path was found later
            continue;
        }
        for (uint i = 0; i < g[v].size(); i++) {
            Edge e = g[v][i];
            uint k = e.to;
            pr(lv(i) lv(e.to) lv(e.cost))
            if (cost[k] > cost[v] + e.cost) {
                cost[k] = cost[v] + e.cost;
                orig[k] = v;
                pr(ls("neighbour") lv(v) lv(k) lv(e.cost) lv(cost[k]));
                q.push(Vert(k, cost[k]));
            }
        }
    }
    pr(ls("end"))
}
void bfs(uint r, uint w, uint n, const vector<vector<uint>>& g, vector<bool>& visited) {
    visited.resize(n);
    fill(visited.begin(), visited.end(), false);
    stack<uint> st;
    st.push(r);
    visited[r] = true;
    visited[w] = true; // do not enter
    pr(ls("in") lv(r))
    while (!st.empty()) {
        uint v = st.top();
        st.pop();
        for (uint x: g[v]) {
            if (!visited[x]) {
                visited[x] = true;
                pr(ls("in") lv(v) lv(x))
                st.push(x);
            } 
        }
    }
}

vector<bool> make_on_path(uint s, uint t, uint n, const vector<vector<Edge>>& g) {
    vector<uint> orig;
    vector<ull> cost;
    djikstra(s, n, g, orig, cost);
    vector<vector<uint>> r_orig(n, vector<uint>());
    for (uint i = 0; i < n; i++) {
        pr(lv(i) lv(orig[i]))
        r_orig[orig[i]].push_back(i);
    }
    vector<bool> is_on_path;
    bfs(s, t, n, r_orig, is_on_path);
    for (uint i = 0; i < n; i++) {
        pr(lv(i) lv(is_on_path[i]))
    }
    djikstra(t, n, g, orig, cost);
    fill(r_orig.begin(), r_orig.end(), vector<uint>());
    for (uint i = 0; i < n; i++) {
        r_orig[orig[i]].push_back(i);
    }
    vector<bool> is_on_t;
    bfs(t, s, n, r_orig, is_on_t);
    for (uint i = 0; i < n; i++) {
        if (!is_on_t[i]) {
            is_on_path[i] = false;
        }
    }
    return is_on_path;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    uint n, m, s, t, u, v;
    cin >> n >> m;
    cin >> s >> t;
    cin >> u >> v;
    s--;
    t--;
    u--;
    v--;
    pr(lv(s) lv(t) lv(u) lv(v))
    vector<vector<Edge>> g(n, vector<Edge>());
    for (uint i = 0; i < m; i++) {
        uint a, b;
        ull c;
        cin >> a >> b >> c;
        a--;
        b--;
        pr(ls(a) ls("->") ls(b))
        g[a].push_back(Edge(b, c));
        g[b].push_back(Edge(a, c));
    }
    vector<bool> on_path = make_on_path(s, t, n, g);
    for (uint i = 0; i < n; i++) {
        pr(lv(i) lv(on_path[i]))
    }
    vector<uint> orig;
    vector<ull> cost;
    djikstra(u, n, g, orig, cost);
    ull cost_to_v = cost[v];
    ull cost_to_path = ll_inf;
    for (uint i = 0; i < n; i++) {
        if (!on_path[i]) continue;
        pr(lv(i) lv(cost[i]))
        cost_to_path = min(cost_to_path, cost[i]);
    }
    djikstra(v, n, g, orig, cost);
    ull cost_from_path = ll_inf;
    for (uint i = 0; i < n; i++) {
        if (!on_path[i]) continue;
        cost_from_path = min(cost_from_path, cost[i]);
    }
    ull min_cost = min(cost_from_path + cost_to_path, cost_to_v);
    pr(lv(min_cost) lv(cost_from_path) lv(cost_to_path) lv(cost_to_v))
    cout << min_cost << '\n';
}

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