Submission #753336

#	Time	Username	Problem	Language	Result	Execution time	Memory
753336		Kihihihi	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	170 ms	7228 KiB

ho_t4

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

short skip_cin = 0;
const long long INF = 1e17, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

struct edge
{
    long long to, w, idx;
};

long long n;
vector<edge> g[200], rg[200];

void dijkstra(long long s, vector<long long>& dist, vector<pair<long long, long long>>& p, bool rev, long long del = -1)
{
    if (rev)
    {
        swap(g, rg);
    }

    dist[s] = 0;
    vector<bool> used(n);
    while (true)
    {
        long long v = -1;
        for (long long i = 0; i < n; i++)
        {
            if (!used[i] && dist[i] != INF && (v == -1 || dist[i] < dist[v]))
            {
                v = i;
            }
        }
        if (v == -1)
        {
            break;
        }

        used[v] = true;
        for (auto& i : g[v])
        {
            if (i.idx == del)
            {
                continue;
            }

            if (dist[v] + i.w < dist[i.to])
            {
                dist[i.to] = dist[v] + i.w;
                p[i.to] = { v, i.idx };
            }
        }
    }

    if (rev)
    {
        swap(g, rg);
    }
}

vector<long long> get_path(long long a, long long b, vector<pair<long long, long long>>& p)
{
    if (p[b].first == -1)
    {
        return {};
    }

    vector<long long> res;
    while (b != a)
    {
        res.push_back(p[b].second);
        b = p[b].first;
    }
    return res;
}

void solve()
{
    long long m;
    cin >> n >> m;
    vector<long long> rv(m), w(m);
    vector<pair<long long, long long>> frto(m);
    for (long long i = 0; i < m; i++)
    {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        a--; b--;
        g[a].push_back({ b, c, i });
        rg[b].push_back({ a, c, i });
        rv[i] = d;
        frto[i] = { a, b };
        w[i] = c;
    }

    vector<long long> da(n, INF), db(n, INF), rda(n, INF), rdb(n, INF);
    vector<pair<long long, long long>> pa(n, { -1, -1 }), pb(n, { -1, -1 }), TRASH(n);
    dijkstra(0, da, pa, false);
    dijkstra(n - 1, db, pb, false);
    dijkstra(0, rda, TRASH, true);
    dijkstra(n - 1, rdb, TRASH, true);

    vector<long long> ea = get_path(0, n - 1, pa), eb = get_path(n - 1, 0, pb);
    vector<bool> used(m);
    for (auto& i : ea)
    {
        used[i] = true;
    }
    for (auto& i : eb)
    {
        used[i] = true;
    }

    long long ans = min(INF, da[n - 1] + db[0]);
    for (long long i = 0; i < m; i++)
    {
        auto [x, y] = frto[i];
        if (!used[i])
        {
            ans = min(ans, rv[i] + min(da[n - 1], da[y] + w[i] + rdb[x]) + min(db[0], db[y] + w[i] + rda[x]));
            continue;
        }

        g[y].push_back({ x, w[i], INF });
        vector<long long> fucka(n, INF), fuckb(n, INF);
        dijkstra(0, fucka, TRASH, false, i);
        dijkstra(n - 1, fuckb, TRASH, false, i);
        ans = min(ans, fucka[n - 1] + fuckb[0] + rv[i]);
        g[y].pop_back();
    }
    cout << (ans == INF ? -1 : ans) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

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

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 63 / 63