Submission #442789

#	Time	Username	Problem	Language	Result	Execution time	Memory
442789		arujbansal	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	104 ms	3276 KiB

ho_t4

#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;
    // for (const auto &x : dist_t)
    //     dbg(x);
    inp_g.construct_path(1);

    // dbg(inp_g.par[1]);

    for (int i = 1; i < sz(inp_g.path); i++) {
        // dbg(i, 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++) {
        // dbg(i, 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]) {
                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, sz(edges[u][v]) > 1 ? edges[u][v][1].first : INF);
                inp_g.set_directional_edge(v, u, edges[u][v][0].first + edges[u][v][0].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);
                // int cost1 = inp_g.dist[N] + dist_t[1];

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

                inp_g.set_directional_edge(u, v, inp_g_edge_uv);
                inp_g.set_directional_edge(v, u, inp_g_edge_vu);

                // 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, sz(edges[u][v]) > 1 ? edges[u][v][1].first : INF);
                // inp_g.set_directional_edge(v, u, edges[u][v][0].first + edges[u][v][0].second);
                // inp_g.run(vector<int>{1});
                // inp_g.set_directional_edge(u, v, inp_g_edge_uv);
                // inp_g.set_directional_edge(v, u, inp_g_edge_vu);

                // int inp_g_rev_edge_uv = inp_g_rev.get_edge(u, v);
                // int inp_g_rev_edge_vu = inp_g_rev.get_edge(v, u);
                // inp_g_rev.set_directional_edge(u, v, sz(edges[u][v]) > 1 ? edges[u][v][1].first : INF);
                // inp_g_rev.set_directional_edge(v, u, edges[u][v][0].first + edges[u][v][0].second);
                // inp_g_rev.run(vector<int>{N});
                // inp_g_rev.set_directional_edge(u, v, inp_g_rev_edge_uv);
                // inp_g_rev.set_directional_edge(v, u, inp_g_rev_edge_vu);

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

            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
                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
                ans = min({ans, cost1, cost2});

                // dbg(u, v, k, edges[u][v][k].first, edges[u][v][k].second);
                // dbg(dist_s_rev[u], dist_t[v]);
                // dbg(dist_s[v], dist_t_rev[u]);
                // dbg_out();
                // dbg_out();
            }
        }
    }

    cout << (ans >= 1e18 ? -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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63