oj.uz

Submission #1063083

# Submission time Handle Problem Language Result Execution time Memory
1063083 2024-08-17T14:01:26 Z _8_8_ Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 621 ms 9020 KB 
#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 1e5 + 12, MOD = (int)1e9 + 7;
#define int ll
const ll inf = 1e16;
int n,m;
int U[N],V[N],C[N],D[N];
void dijkstra(int ver,vector<ll> &d,vector<int> &pr) {
    d.resize(n);
    pr.resize(n);
    for(int i = 0;i < n;i++) {
        d[i] = inf;
    }
    d[ver] = 0;
    vector<int> vis(n,0);
    vector<vector<int>> g;g.resize(n);
    for(int i = 0;i < m;++i) {
        g[U[i]].push_back(i);
    }
    for(int i = 0;i < n;i++) {
        int v = -1;
        for(int j = 0;j < n;j++) {
            if(vis[j]) continue;
            if(v == -1 || d[j] < d[v]) {
                v = j;
            }
        }
        vis[v] = 1;
        for(int t:g[v]) {
            int to = V[t],w = C[t];
            if(d[to] > d[v] + w) {
                d[to] = d[v] + w;
                pr[to] = t;
            }
        }
    }
}
vector<ll> d[N];
vector<int> p[N];
ll res = inf;
bool in[N];
void test() {
    cin >> n >> m;
    for(int i = 0;i < m;i++) {
        cin >> U[i] >> V[i] >> C[i] >> D[i];
        U[i]--;V[i]--;
    }
    for(int i = 0;i < n;++i) {
        dijkstra(i,d[i],p[i]);
    }
    res = d[0][n-1] + d[n - 1][0];
    vector<ll> bfd;
    vector<int> bfp;
    // for(int j = 0;j < m;j++) {
    //     in[j] = 1;
    //     swap(V[j],U[j]);
    //     ll nv = D[j];
    //     dijkstra(0,bfd,bfp);
    //     nv += bfd[n - 1];
    //     dijkstra(n - 1,bfd,bfp);
    //     nv += bfd[0];
    //     res = min(res,nv);
    //     swap(V[j],U[j]);
    // }
    auto make = [&](int j){
        in[j] = 1;
        swap(V[j],U[j]);
        ll nv = D[j];
        dijkstra(0,bfd,bfp);
        nv += bfd[n - 1];
        dijkstra(n - 1,bfd,bfp);
        nv += bfd[0];
        res = min(res,nv);
        swap(V[j],U[j]);
    };
    for(int i = 0;i < n - 1;i++) {
        if(d[0][i] != inf && i != 0) {
            make(p[0][i]);
        }   
        if(d[n - 1][i] != inf && i != n - 1) {
            make(p[n - 1][i]);
        }
    }
    for(int i = 0;i < m;i++) {
        if(in[i]) continue;

        swap(U[i],V[i]);
        ll val = min(d[0][n - 1],d[0][U[i]] + d[V[i]][n - 1] + C[i] + D[i]);
        val += min(d[n - 1][0],d[n - 1][U[i]] + d[V[i]][0] + C[i] + D[i]);
        res = min(res,val);
    }
    if(res >= inf) res = -1;
    cout << res << '\n';
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int t = 1; 
    // cin >> t;
    while(t--) {
        test();
    }
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5724 KB Output is correct
2 Correct 17 ms 5800 KB Output is correct
3 Correct 90 ms 5788 KB Output is correct
4 Correct 90 ms 5784 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 20 ms 5724 KB Output is correct
7 Incorrect 2 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 8472 KB Output is correct
2 Correct 590 ms 8980 KB Output is correct
3 Correct 621 ms 9020 KB Output is correct
4 Correct 108 ms 5720 KB Output is correct
5 Correct 77 ms 5876 KB Output is correct
6 Correct 18 ms 5720 KB Output is correct
7 Correct 22 ms 5720 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Incorrect 362 ms 8968 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 5720 KB Output is correct
2 Correct 29 ms 5724 KB Output is correct
3 Correct 432 ms 8524 KB Output is correct
4 Correct 23 ms 5724 KB Output is correct
5 Correct 545 ms 8960 KB Output is correct
6 Incorrect 2 ms 4956 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 5724 KB Output is correct
2 Correct 17 ms 5800 KB Output is correct
3 Correct 90 ms 5788 KB Output is correct
4 Correct 90 ms 5784 KB Output is correct
5 Correct 4 ms 5212 KB Output is correct
6 Correct 20 ms 5724 KB Output is correct
7 Incorrect 2 ms 4956 KB Output isn't correct
8 Halted 0 ms 0 KB -