oj.uz

Submission #1063075

# Submission time Handle Problem Language Result Execution time Memory
1063075 2024-08-17T13:56:38 Z _8_8_ Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 143 ms 9048 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 x,int y,vector<int> &pr){
        while(x != y) {
            int j = pr[x];
            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]);
            x = U[j];
        }
    };
    if(d[0][n - 1] != inf) make(n - 1,0,p[0]);
    if(d[n - 1][0] != inf) make(0,n - 1,p[n - 1]);
    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 26 ms 5724 KB Output is correct
2 Correct 17 ms 5664 KB Output is correct
3 Correct 25 ms 5852 KB Output is correct
4 Correct 25 ms 5724 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 18 ms 5720 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 93 ms 5848 KB Output is correct
11 Correct 98 ms 5724 KB Output is correct
12 Correct 91 ms 5716 KB Output is correct
13 Incorrect 21 ms 5720 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 8368 KB Output is correct
2 Correct 143 ms 8148 KB Output is correct
3 Correct 137 ms 8172 KB Output is correct
4 Correct 26 ms 5724 KB Output is correct
5 Correct 23 ms 5736 KB Output is correct
6 Correct 18 ms 5724 KB Output is correct
7 Correct 17 ms 5720 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Incorrect 127 ms 8120 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5724 KB Output is correct
2 Correct 18 ms 5720 KB Output is correct
3 Correct 101 ms 7628 KB Output is correct
4 Correct 17 ms 5724 KB Output is correct
5 Correct 122 ms 9048 KB Output is correct
6 Correct 2 ms 4956 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Incorrect 118 ms 9016 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5724 KB Output is correct
2 Correct 17 ms 5664 KB Output is correct
3 Correct 25 ms 5852 KB Output is correct
4 Correct 25 ms 5724 KB Output is correct
5 Correct 3 ms 5208 KB Output is correct
6 Correct 18 ms 5720 KB Output is correct
7 Correct 2 ms 4956 KB Output is correct
8 Correct 2 ms 4956 KB Output is correct
9 Correct 2 ms 5212 KB Output is correct
10 Correct 93 ms 5848 KB Output is correct
11 Correct 98 ms 5724 KB Output is correct
12 Correct 91 ms 5716 KB Output is correct
13 Incorrect 21 ms 5720 KB Output isn't correct
14 Halted 0 ms 0 KB -