Submission #442471

#	Time	Username	Problem	Language	Result	Execution time	Memory
442471		Aryan_Raina	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1097 ms	7172 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, INF);

    priority_queue<ar<int,3>, vector<ar<int,3>>, greater<ar<int,3>>> pq;
    pq.push({0, s, -1});

    while (!pq.empty()) {
        auto [d, u, e] = pq.top(); pq.pop();
        if (dist[u] <= d) continue;
        dist[u] = d; prev[u] = e;

        for (auto [v, i] : g[typ][u]) if (dist[v] > d+w[i])
            pq.push({d+w[i], v, i});
    }

    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, INF);

    priority_queue<ar<int,2>, vector<ar<int,2>>, greater<ar<int,2>>> pq;
    pq.push({0, s});

    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (dist[u] <= d) continue;
        dist[u] = d;

        for (auto [v, i] : g[0][u]) if (dist[v] > d+w[i] && i != reve)
            pq.push({d+w[i], v});

        if (u == b[reve] && dist[a[reve]] > d+w[reve]) 
            pq.push({d+w[reve], a[reve]});
    }

    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: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63