oj.uz

Submission #1115182

# Submission time Handle Problem Language Result Execution time Memory
1115182 2024-11-20T08:12:11 Z staszic_ojuz Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 18 ms 7252 KB 
#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;
constexpr uint int_inf = 1e9;
constexpr ull ll_inf = 2e14;
struct Edge {
    uint from;
    uint to;
    ull cost;
    ull reverse_cost;
    Edge() {}
    Edge(uint from, uint to, uint cost, ull reverse_cost) : from(from), to(to),
     cost(cost), reverse_cost(reverse_cost) {}
};

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

bool operator>(const Verticie& a, const Verticie& b) {
    return a.cost > b.cost;
}

vector<ull> djikstra(const uint r, const vector<vector<Edge>>& g) {
    vector<ull> cost(g.size(), ll_inf);
    priority_queue<Verticie, vector<Verticie>, greater<Verticie>> q;
    q.push(Verticie(r, 0));
    pr(ls("visit") lv(r))
    cost[r] = 0;
    while (!q.empty()) {
        Verticie vv = q.top();
        uint v = vv.i;
        pr(ls("visit") lv(v))
        q.pop();
        for (uint i = 0; i < g[v].size(); i++) {
            uint k = g[v][i].to;
            if (cost[k] < ll_inf) continue;
            if (g[v][i].cost == ll_inf) continue;
            cost[k] = min(cost[k], cost[v] + g[v][i].cost);
            pr(ls("neighbour") lv(v) lv(k) lv(g[v][i].cost))
            q.push(Verticie(g[v][i].to, cost[k]));
        }
    }
    return cost;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    uint n, m;
    cin >> n >> m;
    if (m % 2 == 1) return 1;
    vector<vector<Edge>> g(n*2, vector<Edge>()), orig(n, vector<Edge>());
    uint min_d = 1e9; 
    for (uint i = 0; i < m; i++) {
        uint u, v, c, d;
        cin >> u >> v >> c >> d;
        u--;
        v--;
        pr(ls(u) ls("to") ls(v) lv(c) lv(d))
        g[u].push_back(Edge(u, v, c, d));
        orig[u].push_back(Edge(u, v, c, d));
        g[u+n].push_back(Edge(u+n, v+n, c, d));
        g[v].push_back(Edge(v, u+n, d+c, d));
        min_d = min(min_d, d);
    }
    auto ds = djikstra(0, g);
    uint cost_thru = ds[2*n-1] + djikstra(2*n-1, g)[0];
    uint cost_no = ds[n-1];
    pr(lv(cost_thru) lv(cost_no))
    cout << min(cost_thru, cost_no) << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 7252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -