oj.uz

Submission #958485

# Submission time Handle Problem Language Result Execution time Memory
958485 2024-04-05T22:08:21 Z BhavayGoyal Olympic Bus (JOI20_ho_t4) C++14
0 / 100
 88 ms 8968 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define vi vector<int>
#define vii vector<vector<int>>
#define pii pair<int, int>
#define pb push_back
#define f first
#define s second
#define endl "\n"

const int linf = 1e15;

// -------------------------------------------------- Main Code --------------------------------------------------

const int N = 201, M = 50001;
int n, m;
multiset<pii> g[N];
vii edges;
map<pair<int, int>, bool> isShort;

void dijkstra(int source) {
    priority_queue<pii, vector<pii>, greater<>> q;
    vi vis(n+1, 0), dis(n+1, linf), par(n+1);
    q.push({0, source});
    dis[source] = 0;
    while (!q.empty()) {
        pii f = q.top(); q.pop();
        int src = f.s;
        if (vis[src]) continue;
        vis[src] = true;

        for (auto child : g[src]) {
            int ch = child.f, wt = child.s;
            if (dis[ch] > dis[src] + wt) {
                par[ch] = src;
                dis[ch] = dis[src] + wt;
                q.push({dis[ch], ch});
            }
        }
    }

    int x = (source==1?n:1);
    while (par[x]) {
        isShort[{par[x], x}] = true;
        x = par[x];
    }
}

int get_dist(int s, int t) {
    vi D(n+1, linf);
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    D[s] = 0;
    pq.push({0, s});
    while (pq.size()) {
        auto &[x, u] = pq.top();
        pq.pop();
        if (D[u] == x) {
            for (pii child : g[u]) {
                int v = child.f, wt = child.s;
                if (D[v] > x + wt) {
                    pq.push({D[v] = x + wt, v});
                }
            }
        }
    }
    return D[t];
}


void sol() {
    cin >> n >> m;
    vii dist(n+1, vi(n+1, linf));
    for (int i = 1; i <= n; i++) dist[i][i] = 0;

    for (int i = 1; i <= m; i++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        dist[a][b] = min(dist[a][b], c);
        g[a].insert({b, c});
        edges.pb({a, b, c, d});
    }

    dijkstra(1);
    dijkstra(n);
    
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    int ans = min(linf, dist[1][n] + dist[n][1]);

    for (auto i : edges) {
        int a = i[0], b = i[1], c = i[2], d = i[3];
        if (isShort[{a, b}]) {
            g[a].erase(g[a].find({b, c}));
            g[b].insert({a, c});
            ans = min(ans, get_dist(1, n) + get_dist(n, 1) + d);
            g[b].erase(g[b].find({a, c}));
            g[a].insert({b, c});
        }
        else {
            int A = min(dist[1][n], dist[1][b] + c + dist[a][n]);
            int B = min(dist[n][1], dist[n][b] + c + dist[a][1]);
            ans = min(ans, A + B + d);
        }
    }

    cout << (ans==linf?-1:ans) << endl;
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    // cin >> t; 
    while (t--) {
        sol();
    }
    return 0;
}

Compilation message

ho_t4.cpp: In function 'long long int get_dist(long long int, long long int)':
ho_t4.cpp:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         auto &[x, u] = pq.top();
      |               ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 832 KB Output is correct
3 Correct 8 ms 860 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 12 ms 344 KB Output is correct
10 Incorrect 24 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 8476 KB Output is correct
2 Correct 84 ms 8452 KB Output is correct
3 Correct 80 ms 8452 KB Output is correct
4 Incorrect 9 ms 1116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1112 KB Output is correct
2 Correct 7 ms 600 KB Output is correct
3 Correct 45 ms 7288 KB Output is correct
4 Correct 7 ms 600 KB Output is correct
5 Correct 54 ms 8968 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 42 ms 8872 KB Output is correct
9 Correct 42 ms 8720 KB Output is correct
10 Correct 63 ms 8488 KB Output is correct
11 Correct 48 ms 8460 KB Output is correct
12 Correct 52 ms 8460 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Incorrect 52 ms 8452 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 860 KB Output is correct
2 Correct 7 ms 832 KB Output is correct
3 Correct 8 ms 860 KB Output is correct
4 Correct 9 ms 860 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 9 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 12 ms 344 KB Output is correct
10 Incorrect 24 ms 860 KB Output isn't correct
11 Halted 0 ms 0 KB -