Submission #1259287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259287		wedonttalkanymore	Olympic Bus (JOI20_ho_t4)	C++20	0 / 100	23 ms	5448 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], adj1[N];
pii edge[N][N];
int length[N];
bool check[100005], check1[100005];
int road1[100005], road2[100005];
int dist[N][N];

void dijk(int u, vector <pii> &trace, int cant) {
    for (int i = 1; i <= n; i++) {
        length[i] = inf;
        trace[i] = make_pair(0, 0);
    }
    length[u] = 0;
    priority_queue <pii, vector <pii>, greater <pii> > q;
    q.push({0, u});
    while(q.size()) {
        auto [val, u] = q.top();
        q.pop();
        if (val > length[u]) continue;
        for (auto [v, c, d, id] : adj[u]) {
            if (id == cant) continue;
            if (length[v] > length[u] + c) {
                length[v] = length[u] + c;
                trace[v] = {u, id};
                q.push({length[v], v});
            }
        }
    }
}

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (dist[i][k] >= inf) continue;
            for (int j = 1; j <= n; j++) {
                if (dist[k][j] >= inf) continue;
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

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 <= n; i++) {
        for (int j = 1; j <= n; j++) if (i != j) dist[i][j] = inf; else dist[i][j] = 0;
    }
    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});
        if (dist[u][v] > c) dist[u][v] = c;
    }
    floyd();
    vector <pii> trace1(n + 1, make_pair(0, 0));
    dijk(1, trace1, -1);
    int minn = length[n];
    int t = n;
    while(t > 0) {
        auto [v, id] = trace1[t];
        if (v == 0) break;
        check[id] = true;
        t = v;
    }
    for (int i = 1; i <= m; i++) {
        if (check[i]) {
            dijk(1, trace1, i);
            road1[i] = length[n];
        }
        else road1[i] = minn;
    }
    dijk(n, trace1, -1);
    int minn2 = length[1];
    t = 1;
    while(t > 0) {
        auto [v, id] = trace1[t];
        if (v == 0) break;
        check1[id] = true;
        t = v;
    }
    for (int i = 1; i <= m; i++) {
        if (check1[i]) {
            dijk(n, trace1, i);
            road2[i] = length[1];
        }
        else road2[i] = minn2;
    }
    int ans = inf;
    if (dist[1][n] < inf && dist[n][1] < inf) ans = min(ans, dist[1][n] + dist[n][1]);
    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 (dist[1][u] < inf && dist[v][n] < inf) val1 = dist[1][u] + c + dist[v][n];
        if (dist[n][u] < inf && dist[v][1] < inf) val2 = dist[n][u] + c + dist[v][1];

        if (val1 < inf && road2[i] < inf) {
            __int128 tmp = (__int128)val1 + (__int128)road2[i] + (__int128)d;
            if (tmp < ans) ans = (int)tmp;
        }
        if (val2 < inf && road1[i] < inf) {
            __int128 tmp = (__int128)road1[i] + (__int128)val2 + (__int128)d;
            if (tmp < ans) ans = (int)tmp;
        }
    }

    if (ans >= inf) cout << -1;
    else cout << ans;

    return 0;
}

Compilation message (stderr)

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

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