제출 #591662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
591662		piOOE	Olympic Bus (JOI20_ho_t4)	C++17	0 / 100	91 ms	2560 KiB

ho_t4

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 200, M = 50000;
const ll infL = 3e18;

bool in_s[M], in_n[M], used[N];
ll distS[N], distN[N], distAllS[N], distAllN[N], tmp[N];

int A[M], B[M], W[M], D[M], n, m;

vector<pair<int, int>> newg[N];

void dijkstra(int s, vector<pair<int, int>> g[], ll dist[], bool need, bool in[], int blocked = -1) {
    fill(dist, dist + n, infL);
    dist[s] = 0;
    vector<bool> was(n);
    while (s != -1) {
        was[s] = true;
        for (auto [to, i]: g[s]) {
            if (i != blocked && dist[to] > dist[s] + W[i]) {
                dist[to] = dist[s] + W[i];
            }
        }
        int nxt = -1;
        for (int i = 0; i < n; ++i) {
            if (!was[i] && dist[i] != infL && (nxt == -1 || dist[nxt] > dist[i])) {
                nxt = i;
            }
        }
        s = nxt;
    }
    if (need) {
        for (int i = 0; i < n; ++i) {
            newg[i].clear();
        }
        for (int i = 0; i < n; ++i) {
            for (auto [to, j]: g[i]) {
                if (dist[to] == dist[i] + W[j]) {
                    newg[i].emplace_back(to, j);
                }
            }
        }
        memset(used, 0, sizeof(used[0]) * n);
        function<void(int)> dfs = [&](int v) {
            used[v] = true;
            for (auto [to, i]: newg[v]) {
                if (!used[to]) {
                    in[i] = true;
                    dfs(to);
                }
            }
        };
        dfs(s);
    }
}

vector<pair<int, int>> g[N], revg[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> A[i] >> B[i] >> W[i] >> D[i];
        --A[i], --B[i];
        g[A[i]].emplace_back(B[i], i);
        revg[B[i]].emplace_back(A[i], i);
    }
    dijkstra(0, g, distS, true, in_s);
    dijkstra(0, revg, distAllS, false, used);
    dijkstra(n - 1, g, distN, true, in_n);
    dijkstra(n - 1, revg, distAllN, false, used);
    ll ans = infL;
    ans = min(ans, distS[n - 1] + distN[0]);
    for (int i = 0; i < m; ++i) {
        ll valSN, valNS;
        if (in_s[i]) {
            dijkstra(0, g, tmp, false, nullptr, i);
            valSN = tmp[n - 1];
        } else {
            valSN = min(distS[n - 1], distS[B[i]] + W[i] + distAllN[A[i]]);
        }
        if (in_n[i]) {
            dijkstra(n - 1, g, tmp, false, nullptr, i);
            valNS = tmp[0];
        } else {
            valNS = min(distN[0], distN[B[i]] + W[i] + distAllS[A[i]]);
        }
        ans = min(ans, D[i] + valNS + valSN);
    }
    cout << (ans == infL ? -1 : ans);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t4.cpp: In function 'void dijkstra(int, std::vector<std::pair<int, int> >*, ll*, bool, bool*, int)':
ho_t4.cpp:49:19: warning: array subscript -1 is below array bounds of 'bool [200]' [-Warray-bounds]
   49 |             used[v] = true;
      |             ~~~~~~^
ho_t4.cpp:10:24: note: while referencing 'used'
   10 | bool in_s[M], in_n[M], used[N];
      |                        ^~~~

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