oj.uz

Submission #820016

# Submission time Handle Problem Language Result Execution time Memory
820016 2023-08-10T17:42:08 Z vjudge1 Olympic Bus (JOI20_ho_t4) C++17
11 / 100
 19 ms 4116 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 1000;
const int M = 100000;
const ll INF = 1e18;

int n, m;
vector<pair<int, int>> g[N], g0[N];
ll C[M], D[M];
pair<int, int> edges[M];

vector<ll> dijkstra(int s, vector<pair<int, int>> g[]) {
    vector<ll> dist(n + 1, INF);
    dist[s] = 0;
    set<pair<ll, int>> st; 
    for(int i = 1; i <= n; i++) 
        st.insert({dist[i], i});
    while(!st.empty()) {
        s = st.begin()->second;
        st.erase(st.begin());
        for(auto [to, i] : g[s]) {
            if(dist[to] > dist[s] + C[i]) {
                st.erase({dist[to], to});
                dist[to] = dist[s] + C[i];
                st.insert({dist[to], to});
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[i] = {u, v};
        cin >> C[i] >> D[i];
        g[u].push_back({v, i});
        g0[v].push_back({u, i});
    }
    auto d1 = dijkstra(1, g);
    auto dn = dijkstra(n, g);
    auto e1 = dijkstra(1, g0);
    auto en = dijkstra(n, g0);
    ll res = d1[n] + dn[1];
    for(int i = 0; i < m; i++) {
        auto [u, v] = edges[i];
        res = min(res, d1[v] + en[u] + dn[1] + C[i] + D[i]);
        res = min(res, dn[v] + e1[u] + d1[n] + C[i] + D[i]);
        res = min(res, d1[v] + en[u] + dn[v] + e1[u] + 2 * C[i] + D[i]);
    }
    if(res >= INF) res = -1;    
    cout << res;
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 3880 KB Output is correct
2 Correct 19 ms 3840 KB Output is correct
3 Correct 15 ms 4056 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 388 KB Output is correct
6 Correct 1 ms 444 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 376 KB Output is correct
9 Correct 15 ms 4052 KB Output is correct
10 Correct 16 ms 3968 KB Output is correct
11 Correct 16 ms 3972 KB Output is correct
12 Correct 15 ms 4008 KB Output is correct
13 Correct 15 ms 4052 KB Output is correct
14 Correct 15 ms 4116 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 11 ms 2920 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 14 ms 3668 KB Output is correct
6 Incorrect 1 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 0 ms 340 KB Output isn't correct
8 Halted 0 ms 0 KB -