oj.uz

Submission #442824

# Submission time Handle Problem Language Result Execution time Memory
442824 2021-07-09T08:00:58 Z arujbansal Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 3140 KB 
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int long long

template<typename T>
struct Dijkstra {
    // const T INF = numeric_limits<T>::max();
    const T INF = 1e18;

    int n;
    vector<vector<T>> adj;
    vector<T> dist;
    vector<int> par, path;

    Dijkstra(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        adj.assign(n, vector<T>(n + 1, INF));
    }

    void minimise_directional_edge(int u, int v, T wt) {
        adj[u][v] = min(adj[u][v], wt);
    }

    void minimise_bidirectional_edge(int u, int v, T wt) {
        minimise_directional_edge(u, v, wt);
        minimise_directional_edge(v, u, wt);
    }

    void set_directional_edge(int u, int v, T wt) {
        adj[u][v] = wt;
    }

    void set_bidirectional_edge(int u, int v, T wt) {
        set_directional_edge(u, v, wt);
        set_directional_edge(v, u, wt);
    }

    T get_edge(int u, int v) {
        return adj[u][v];
    }

    void run(vector<int> src) {
        vector<bool> vis(n, false);
        dist.assign(n, INF);
        par.assign(n, -1);
        path.clear();

        for (const auto &node : src)
            dist[node] = 0;

        while (true) {
            pair<T, int> mn = make_pair(INF, -1);

            for (int u = 0; u < n; u++) {
                if (!vis[u])
                    mn = min(mn, make_pair(dist[u], u));
            }

            if (mn.first >= INF) break;
            vis[mn.second] = true;

            for (int v = 0; v < n; v++) {
                if (adj[mn.second][v] >= INF) continue;

                T new_dist = mn.first + adj[mn.second][v];

                if (new_dist < dist[v]) {
                    dist[v] = new_dist;
                    par[v] = mn.second;
                }
            }
        }
    }

    void construct_path(int dest) {
        path.clear();

        path.push_back(dest);
        while (par[path.back()] > -1)
            path.push_back(par[path.back()]);

        reverse(path.begin(), path.end());
    }

    bool reachable(int node) {
        return par[node] > -1;
    }
};

const int MXN = 205, INF = 1e18;
vector<pair<int, int>> edges[MXN][MXN];
bool in_path[MXN][MXN];

void solve() {
    int N, M;
    cin >> N >> M;

    Dijkstra<int> inp_g(N + 1), inp_g_rev(N + 1);

    while (M--) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;

        inp_g.minimise_directional_edge(u, v, c);
        inp_g_rev.minimise_directional_edge(v, u, c);
        edges[u][v].emplace_back(c, d);
    }

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            sort(all(edges[i][j]));
        }
    }

    inp_g.run(vector<int>{N});
    vector<int> dist_t = inp_g.dist;
    inp_g.construct_path(1);

    for (int i = 1; i < sz(inp_g.path); i++)
        in_path[inp_g.path[i - 1]][inp_g.path[i]] = true;

    inp_g.run(vector<int>{1});
    vector<int> dist_s = inp_g.dist;
    inp_g.construct_path(N);

    for (int i = 1; i < sz(inp_g.path); i++)
        in_path[inp_g.path[i - 1]][inp_g.path[i]] = true;

    inp_g_rev.run(vector<int>{1});
    vector<int> dist_s_rev = inp_g_rev.dist;

    inp_g_rev.run(vector<int>{N});
    vector<int> dist_t_rev = inp_g_rev.dist;

    int ans = dist_s[N] + dist_t[1];

    for (int u = 1; u <= N; u++) {
        for (int v = 1; v <= N; v++) {
            if (edges[u][v].empty()) continue;
            // if (in_path[u][v]) {
            for (int k = 0; k < sz(edges[u][v]); k++) {
                int inp_g_edge_uv = inp_g.get_edge(u, v);
                int inp_g_edge_vu = inp_g.get_edge(v, u);
                inp_g.set_directional_edge(u, v, k > 0 ? edges[u][v][0].first : (sz(edges[u][v]) > 1 ? edges[u][v][1].first : INF));
                inp_g.set_directional_edge(v, u, edges[u][v][k].first + edges[u][v][k].second);

                inp_g.run(vector<int>{1});
                int cost = inp_g.dist[N];

                inp_g.run(vector<int>{N});
                cost += inp_g.dist[1];

                ans = min(ans, cost);
    
                inp_g.set_directional_edge(u, v, inp_g_edge_uv);
                inp_g.set_directional_edge(v, u, inp_g_edge_vu);
            }
            // }

            // for (int k = 0 + (in_path[u][v]); k < sz(edges[u][v]); k++) {
            //     int cost1 = edges[u][v][k].first + edges[u][v][k].second + dist_s_rev[u] + dist_t[v] + dist_s[N]; // T to S
            //     // cost1 = min(cost1, edges[u][v][k].first + edges[u][v][k].second + dist_s_rev[u] + dist_t[v] + dist_s[N]);

            //     int cost2 = edges[u][v][k].first + edges[u][v][k].second + dist_s[v] + dist_t_rev[u] + dist_t[1]; // S to T
            //     // cost2 = min(cost2, edges[u][v][k].first + edges[u][v][k].second + dist_s[u] + dist_t_rev[v] + dist_t[1]);

            //     ans = min({ans, cost1, cost2});
            // }
        }
    }

    cout << (ans >= INF ? -1 : ans);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 1996 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 310 ms 1996 KB Output is correct
4 Correct 323 ms 2008 KB Output is correct
5 Correct 13 ms 1360 KB Output is correct
6 Correct 5 ms 1868 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Correct 1 ms 1228 KB Output is correct
9 Correct 2 ms 1228 KB Output is correct
10 Correct 319 ms 2032 KB Output is correct
11 Correct 330 ms 2116 KB Output is correct
12 Correct 326 ms 2048 KB Output is correct
13 Incorrect 199 ms 1996 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1083 ms 3140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 2024 KB Output is correct
2 Correct 22 ms 1868 KB Output is correct
3 Execution timed out 1086 ms 2992 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 1996 KB Output is correct
2 Correct 3 ms 1868 KB Output is correct
3 Correct 310 ms 1996 KB Output is correct
4 Correct 323 ms 2008 KB Output is correct
5 Correct 13 ms 1360 KB Output is correct
6 Correct 5 ms 1868 KB Output is correct
7 Correct 1 ms 1228 KB Output is correct
8 Correct 1 ms 1228 KB Output is correct
9 Correct 2 ms 1228 KB Output is correct
10 Correct 319 ms 2032 KB Output is correct
11 Correct 330 ms 2116 KB Output is correct
12 Correct 326 ms 2048 KB Output is correct
13 Incorrect 199 ms 1996 KB Output isn't correct
14 Halted 0 ms 0 KB -