Submission #254916

#	Time	Username	Problem	Language	Result	Execution time	Memory
254916		imeimi2000	Olympic Bus (JOI20_ho_t4)	C++17	21 / 100	496 ms	3448 KiB

ho_t4

#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 = U[i]; j != b; j = V[prev2[j]]) if (i == prev2[j]) { r = 1; break; }
        if (!r) {
            ans[i] += 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
• Subtask 2: 0 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63