oj.uz

Submission #203168

# Submission time Handle Problem Language Result Execution time Memory
203168 2020-02-19T15:30:47 Z godwind Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 49 ms 2356 KB 
// 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;
            }
        }
        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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 8 ms 380 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 38 ms 460 KB Output is correct
11 Correct 49 ms 464 KB Output is correct
12 Incorrect 46 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2344 KB Output is correct
2 Correct 40 ms 2348 KB Output is correct
3 Correct 40 ms 2356 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 33 ms 2348 KB Output is correct
10 Correct 32 ms 2344 KB Output is correct
11 Correct 39 ms 2340 KB Output is correct
12 Correct 36 ms 2352 KB Output is correct
13 Incorrect 36 ms 2352 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 29 ms 2100 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 30 ms 2348 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 29 ms 2340 KB Output is correct
9 Correct 27 ms 2344 KB Output is correct
10 Correct 29 ms 2344 KB Output is correct
11 Correct 29 ms 2348 KB Output is correct
12 Correct 28 ms 2352 KB Output is correct
13 Correct 4 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Correct 5 ms 376 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 5 ms 376 KB Output is correct
19 Correct 29 ms 2344 KB Output is correct
20 Incorrect 28 ms 2348 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 7 ms 376 KB Output is correct
4 Correct 8 ms 380 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 38 ms 460 KB Output is correct
11 Correct 49 ms 464 KB Output is correct
12 Incorrect 46 ms 376 KB Output isn't correct
13 Halted 0 ms 0 KB -