Submission #1115407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115407		staszic_ojuz	Commuter Pass (JOI18_commuter_pass)	C++17	0 / 100	252 ms	262144 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, 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))
        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]));
            }
        }
    }
}

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--;
        g[a].push_back(Edge(b, c));
        pr(ls(a) ls("->") ls(b))
        g[b].push_back(Edge(a, c));
    }
    vector<uint> orig;
    vector<ull> cost;
    djikstra(s, n, g, orig, cost);
    vector<uint> path;
    vector<vector<bool>> to_change(n, vector<bool>(n, false));
    uint curr = t;
    while (curr != s) {
        pr(lv(curr) lv(orig[curr]))
        to_change[curr][orig[curr]] = true;
        curr = orig[curr];
    }
    for (uint i = 0; i < n; i++) {
        for (Edge &e : g[i]) {
            if (to_change[i][e.to] || to_change[e.to][i]) {
                e.cost = 0;
                pr(ls(i) ls("->") ls(e.to) lv(e.cost))
            }
        }
    }
    orig.clear();
    cost.clear();
    djikstra(u, n, g, orig, cost);
    for (uint i = 0; i < n; i++) {
        pr(lv(i) lv(orig[i]) lv(cost[i]))
    }
    cout << cost[v] << '\n';
}

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