Submission #203169

#	Time	Username	Problem	Language	Result	Execution time	Memory
203169		godwind	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	346 ms	2356 KiB

ho_t4

// O O O O O O O O O O O O O O O OO O OO O OO O O O TTCH O TTTCH O TTTCH O O O O
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx")
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <cstdio>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
// #include <random>
#include <iomanip>
#include <bitset>
#include <cassert>
 
using namespace std;


#define y1 y11
#define double long double
#define less less228
#define left left228
#define right right228
#define list list228
 
 
 
template<typename T> void uin(T &a, T b) {
    if (b < a) a = b;
}
template<typename T> void uax(T &a, T b) {
    if (b > a) a = b;
}
 
 
// random_device rnd;
 
// template<typename T> void shuffle(vector< T > &v) {
//     for (int i = 1; i < (int)v.size(); ++i) {
//         swap(v[rnd() % i], v[i]);
//     }
//     for (int i = (int)v.size() - 1; i; --i) {
//         swap(v[rnd() % i], v[i]);
//     }
// }

const int N = 228;
const int M = 50 * 1000 + 228;
const int INF = 1e9 + 228;

struct Edge
{
    int u, v, c, d;
    Edge() {}
    Edge(int _u, int _v, int _c, int _d) {u = _u, v = _v, c = _c, d = _d;}
};

int n, m;
int U[M], V[M], C[M], D[M];
bool taken[M];
int from1[N], fromn[N], to1[N], ton[N];
int d[N], pr[N];
vector<int> g[N];
priority_queue< pair<int, int> > q;

int kekos(int s, int t) {
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
        pr[i] = -1;
    }
    d[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        pair<int, int> P = q.top();
        q.pop();
        int v = P.second;
        for (int i : g[v]) {
            if (d[v] + C[i] < d[V[i]]) {
                d[V[i]] = d[v] + C[i];
                pr[V[i]] = i;
                q.push({-d[V[i]], V[i]});
            }
        }
    }
    int x = d[t];
    if (x == INF) return x;
    while (t != s) {
        taken[pr[t]] = 1;
        t = U[pr[t]];
    }
    return x;
}

int dij(int s, int t) {
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
    }
    d[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        pair<int, int> P = q.top();
        q.pop();
        int v = P.second;
        for (int i : g[v]) {
            if (d[v] + C[i] < d[V[i]]) {
                d[V[i]] = d[v] + C[i];
                q.push({-d[V[i]], V[i]});
            }
        }
    }
    return d[t];
}

bool used[N];

int fast_dij(int s, int t) {
    for (int i = 1; i <= n; ++i) {
        d[i] = INF;
    }
    memset(used, 0, sizeof used);
    d[s] = 0;
    for (int it = 0; it < n; ++it) {
        int v = 0;
        for (int i = 1; i <= n; ++i) {
            if (!used[i]) {
                if (v == 0 || d[i] < d[v]) v = i;
            }
        }
        used[v] = 1;
        for (int i : g[v]) {
            if (d[v] + C[i] < d[V[i]]) {
                d[V[i]] = d[v] + C[i];
            }
        }
    }
    return d[t];
}

void reset() {
    for (int i = 1; i <= n; ++i) {
        g[i].clear();
    }
    for (int i = m - 1; i + 1; --i) {
        g[U[i]].push_back(i);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    vector< Edge > edges;
    for (int i = 0; i < m; ++i) {
        cin >> U[i] >> V[i] >> C[i] >> D[i];
        edges.emplace_back(U[i], V[i], C[i], D[i]);
        g[U[i]].emplace_back(i);
    }
    int path1 = kekos(1, n);
    int path2 = kekos(n, 1);
    int answer = 2 * INF;
    if (path1 != INF && path2 != INF) {
        uin(answer, path1 + path2);
    }
    dij(1, 0);
    for (int i = 1; i <= n; ++i) {
        from1[i] = d[i];
    }
    dij(n, 0);
    for (int i = 1; i <= n; ++i) {
        fromn[i] = d[i];
    }
    for (int i = 0; i < m; ++i) {
        swap(U[i], V[i]);
    }
    reset();
    dij(1, 0);
    for (int i = 1; i <= n; ++i) {
        to1[i] = d[i];
    }
    dij(n, 0);
    for (int i = 1; i <= n; ++i) {
        ton[i] = d[i];
    }
    for (int i = 0; i < m; ++i) {
        swap(U[i], V[i]);
    }
    reset();
    for (int E = 0; E < m; ++E) {
        if (!taken[E]) {
            int npath1 = min(path1, from1[V[E]] + ton[U[E]] + C[E]);
            int npath2 = min(path2, fromn[V[E]] + to1[U[E]] + C[E]);
            if (npath1 < INF && npath2 < INF) {
                uin(answer, D[E] + npath1 + npath2);
            }
        } else {
            swap(U[E], V[E]);
            reset();
            int go1 = fast_dij(1, n);
            if (go1 < INF) {
                int go2 = fast_dij(n, 1);
                if (go2 < INF) {
                    uin(answer, D[E] + go1 + go2);
                }
            }
            swap(U[E], V[E]);
        }
    }
    if (answer > 2 * INF - 1000000) answer = -1;
    cout << answer << '\n';
    return 0;
}
// RU_023
 
/*
4 5
1 2 4 4
1 3 2 1
4 3 1 2
4 1 6 1
2 4 2 5
---
10


4 10
1 2 4 4
1 2 4 4
1 3 2 1
1 3 2 1
4 3 1 2
4 3 1 2
4 1 6 1
4 1 6 1
2 4 2 5
2 4 2 5
---
10

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1
---
2



4 5
1 2 4 4
1 3 2 4
4 3 1 5
4 1 6 1
2 4 2 5
---
12


4 5
2 1 4 4
1 3 2 1
4 3 1 2
4 3 6 1
2 4 2 5
---
-1

*/

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