oj.uz

Submission #254918

# Submission time Handle Problem Language Result Execution time Memory
254918 2020-07-30T20:37:28 Z imeimi2000 Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 1000 ms 3576 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long llong;

const llong inf = 1e18;
int n, m;
int U[50001], V[50001], C[50001];

bool used[201];
void dijkstra(vector<int> edge[], llong D[], int P[], int s) {
    for (int i = 1; i <= n; ++i) D[i] = inf, used[i] = 0;
    D[s] = 0;
    while (1) {
        int x = 0;
        llong d = inf;
        for (int i = 1; i <= n; ++i) {
            if (!used[i] && D[i] < d) x = i, d = D[i];
        }
        if (!x) break;
        used[x] = 1;
        for (int it : edge[x]) {
            llong nd = d + C[it];
            int i = U[it] ^ V[it] ^ x;
            if (nd < D[i]) {
                D[i] = nd;
                P[i] = it;
            }
        }
    }
}

llong ans[50001];
llong dist1[201], dist2[201], dist3[201];
int prev1[201], prev2[201], prev3[201];
vector<int> pedge[201], redge[201], edge[201];
void solve(int a, int b) {
    dijkstra(pedge, dist1, prev1, a);
    ans[0] += dist1[b];
    dijkstra(redge, dist2, prev2, b);
    for (int i = 1; i <= m; ++i) {
        if (dist1[V[i]] >= inf || dist2[U[i]] >= inf) {
            ans[i] += inf;
            continue;
        }
        bool r = 0;
        if (!r) for (int j = V[i]; j != a; j = U[prev1[j]]) if (i == prev1[j]) { r = 1; break; }
        if (!r) for (int j = b; j != a; j = U[prev1[j]]) if (i == prev1[j]) { r = 1; break; }
        if (!r) for (int j = U[i]; j != b; j = V[prev2[j]]) if (i == prev2[j]) { r = 1; break; }
        if (!r) {
            ans[i] += min(dist1[b], dist1[V[i]] + C[i] + dist2[U[i]]);
            continue;
        }
        for (int j = 1; j <= n; ++j) edge[j].clear();
        for (int j = 1; j <= m; ++j) {
            edge[i != j ? U[j] : V[j]].push_back(j);
        }
        dijkstra(edge, dist3, prev3, a);
        ans[i] += dist3[b];
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> U[i] >> V[i] >> C[i] >> ans[i];
        pedge[U[i]].push_back(i);
        redge[V[i]].push_back(i);
    }
    solve(1, n); solve(n, 1);
    llong ret = inf;
    for (int i = 0; i <= m; ++i) ret = min(ret, ans[i]);
    printf("%lld\n", ret < inf ? ret : -1);
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 508 KB Output is correct
2 Execution timed out 1032 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 2944 KB Output is correct
2 Correct 458 ms 3064 KB Output is correct
3 Correct 475 ms 3576 KB Output is correct
4 Correct 84 ms 512 KB Output is correct
5 Correct 60 ms 384 KB Output is correct
6 Execution timed out 1092 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 504 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 387 ms 2552 KB Output is correct
4 Execution timed out 1085 ms 384 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 508 KB Output is correct
2 Execution timed out 1032 ms 384 KB Time limit exceeded
3 Halted 0 ms 0 KB -