Submission #1259266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259266		wedonttalkanymore	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	1095 ms	7748 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 200 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 16;

int n, m;
struct item {
    int v, c, d, id;
};
struct node {
    int u, v, c, d;
} a[100005];
vector <item> adj[N], radj[N];
bool check[100005], check1[100005];
int road1[100005], road2[100005];

int lenArr[N];

void dijk_forbid(int src, int cant, vector<item> graph[], int out[]) {
    for (int i = 1; i <= n; i++) out[i] = inf;
    out[src] = 0;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
    q.push({0, src});
    while (!q.empty()) {
        auto t = q.top(); q.pop();
        int val = t.fi, u = t.se;
        if (val > out[u]) continue;
        for (auto it : graph[u]) {
            int v = it.v, c = it.c, id = it.id;
            if (id == cant) continue;
            if (out[v] > out[u] + c) {
                out[v] = out[u] + c;
                q.push({out[v], v});
            }
        }
    }
}

void dijk_no_forbid(int src, vector<item> graph[], int out[]) {
    dijk_forbid(src, -1, graph, out);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        a[i] = {u, v, c, d};
        adj[u].push_back({v, c, d, i});
        radj[v].push_back({u, c, d, i});
    }
    static int from1[N], toN[N], fromN[N], to1[N];
    dijk_no_forbid(1, adj, from1);
    dijk_no_forbid(n, radj, toN);
    dijk_no_forbid(n, adj, fromN);
    dijk_no_forbid(1, radj, to1);
    int ans = inf;
    if (from1[n] < inf && fromN[1] < inf) ans = min(ans, from1[n] + fromN[1]);
    int minn = from1[n], minn2 = fromN[1];
    for (int i = 1; i <= m; i++) {
        int u = a[i].u, v = a[i].v, c = a[i].c;
        if (from1[u] < inf && toN[v] < inf && from1[u] + c + toN[v] == minn) check[i] = true;
    }
    for (int i = 1; i <= m; i++) {
        if (check[i]) {
            dijk_forbid(1, i, adj, lenArr);
            road1[i] = lenArr[n];
        } else road1[i] = minn;
    }
    for (int i = 1; i <= m; i++) {
        int u = a[i].u, v = a[i].v, c = a[i].c;
        if (fromN[u] < inf && to1[v] < inf && fromN[u] + c + to1[v] == minn2) check1[i] = true;
    }
    for (int i = 1; i <= m; i++) {
        if (check1[i]) {
            dijk_forbid(n, i, adj, lenArr);
            road2[i] = lenArr[1];
        } else road2[i] = minn2;
    }
    for (int i = 1; i <= m; i++) {
        if (road1[i] < inf && road2[i] < inf) ans = min(ans, road1[i] + road2[i]);
    }
    for (int i = 1; i <= m; i++) {
        int u = a[i].u, v = a[i].v, c = a[i].c, d = a[i].d;
        int val1 = inf, val2 = inf;
        if (from1[u] < inf && toN[v] < inf) val1 = from1[u] + c + toN[v];
        if (fromN[u] < inf && to1[v] < inf) val2 = fromN[u] + c + to1[v];
        if (val1 < inf && road2[i] < inf) ans = min(ans, val1 + road2[i] + d);
        if (val2 < inf && road1[i] < inf) ans = min(ans, road1[i] + val2 + d);
    }
    if (ans >= inf) cout << -1;
    else cout << ans;
    return 0;
}

Compilation message (stderr)

ho_t4.cpp: In function 'int main()':
ho_t4.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
ho_t4.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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