Submission #442481

#	Time	Username	Problem	Language	Result	Execution time	Memory
442481		Aryan_Raina	Olympic Bus (JOI20_ho_t4)	C++17	21 / 100	31 ms	4592 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define ld long double
#define ar array
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1e9+7;
const int INF = 1e15+5;

const int MXN = 205, MXM = 50005;
vector<ar<int,2>> g[2][MXN];
int a[MXM], b[MXM], w[MXM], revw[MXM], N, M; 
void dijkstra(int s, int t, int typ, vector<int> &dist, vector<bool> &used) {
    vector<int> prev(N, -1); 
    used.resize(M, false); dist.resize(N+1, INF);
    vector<bool> vis(N, false);
    dist[s] = 0;

    while (true) {
        int u = N;
        for (int i = 0; i < N; i++) 
            if (!vis[i] && dist[i] < dist[u])
                u = i;

        if (u == N) break;

        for (auto [v, i] : g[typ][u]) if (dist[v] > dist[u] + w[i])
            dist[v] = dist[u] + w[i], prev[v] = i;

        vis[u] = true;
    }

    if (typ) return;
    for (int cur = t; prev[cur] != -1; cur = a[prev[cur]])
        used[prev[cur]] = true;
}

int getdist(int s, int t, int reve) {
    vector<int> dist(N+1, INF);
    vector<bool> vis(N, false);
    dist[s] = 0;

    while (true) {
        int u = N;
        for (int i = 0; i < N; i++) 
            if (!vis[i] && dist[i] < dist[u])
                u = i;

        if (u == N || dist[t] <= INF/2) break;

        for (auto [v, i] : g[0][u]) if (i != reve)
            dist[v] = min(dist[v], dist[u] + w[i]);

        if (b[reve] == u) 
            dist[a[reve]] = min(dist[a[reve]], dist[u] + w[reve]);

        vis[u] = true;
    }

    return dist[t];
}

void solve() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        cin >> a[i] >> b[i] >> w[i] >> revw[i];
        g[0][--a[i]].push_back({--b[i], i});
        g[1][b[i]].push_back({a[i], i});
    }

    vector<int> to1, toN, from1, fromN;
    vector<bool> used1, usedN, tmp;
    dijkstra(0, N-1, 0, from1, used1);
    dijkstra(N-1, 0, 0, fromN, usedN);
    dijkstra(0, N-1, 1, to1, tmp);
    dijkstra(N-1, 0, 1, toN, tmp);

    int ans = from1[N-1] + fromN[0];
    for (int i = 0; i < M; i++) {
        int tmp = revw[i];

        if (used1[i]) tmp += getdist(0, N-1, i);
        else tmp += min(from1[N-1], from1[b[i]] + toN[a[i]] + w[i]);

        if (usedN[i]) tmp += getdist(N-1, 0, i);
        else tmp += min(fromN[0], fromN[b[i]] + to1[a[i]] + w[i]);

        ans = min(ans, tmp);
    }

    if (ans >= INF/2) cout << -1 << '\n';
    else cout << ans << '\n';
}
 
int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
 
    int t = 1; //cin >> t;
    while (t--) solve();   
}  

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