oj.uz

Submission #974994

# Submission time Handle Problem Language Result Execution time Memory
974994 2024-05-04T09:17:53 Z berr Olympic Bus (JOI20_ho_t4) C++17
0 / 100
 135 ms 8780 KB 
#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int N=205, INF=1e16;


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

    int n, m; cin >> n >> m;
    vector<vector<array<int, 3>>> g(n), g_rev(n);
    vector<array<int, 3>> e(m);
    vector<int> di(m);

    vector<int> all[n][n];
    int cnt =0;
    
    for(auto &[u, v, c]: e){
        cin >> u >> v >> c >> di[cnt];
        u--; v--;
        g[u].push_back({v, c, cnt});
        g_rev[v].push_back({u, c, cnt});
        all[u][v].push_back(cnt);

        cnt++;
    }
    for(int i=0; i<n; i++){
        for(int l=0; l<n; l++){
            sort(all[i][l].begin(), all[i][l].end(), [&](int x, int y){
                return e[x][2] < e[y][2];
            });
        }
    }

    // a = 1 -> i, b = i -> n
    // c = i -> 1 without x
    // d = n -> i without x

    vector a(n+1, vector(n, INF)), b(n+1, vector(n, INF));
    vector c(n+1, vector(n, INF)), d(n+1, vector(n, INF));
    auto dijkstra=[&](int v, int skip, auto& dist, auto&&g){
        dist[v] = 0;
        priority_queue<array<int, 2>> pq;
        pq.push({0, v});

        while(pq.size()){
            auto [cost, v]=pq.top();
            pq.pop(); cost*=-1;
            if(v==skip||dist[v] != cost) continue;

            for(auto [i, l, j]: g[v]){
                if(dist[i] > cost+l){
                    dist[i] = cost+l;
                    pq.push({-dist[i], i});
                }
            }
        }
    };


    for(int i=0; i<=n; i++){
        dijkstra(0, i, a[i], g);
        dijkstra(n-1, i, b[i], g_rev);
        dijkstra(0, i, c[i], g_rev);
        dijkstra(n-1, i, d[i], g);
    }

    int ans=INF;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            //blocklanan edge i ve j arasında

            // 0 -> i // swap j -> n
            //
            if(a[n][i]==INF||b[n][j]==INF) continue;
            int sum=a[n][i]+b[n][j];

            for(auto k: all[j][i]){
                sum+=e[k][2];
                sum+=di[k];

                ans=min(ans, sum+min((i==0)?INF:d[i][0], (j==0)?INF:d[j][0]));
                if(all[j][i].size()>1){
                   /* if(k==all[j][i][0])
                        ans=min(ans, sum+d[j][i]+c[i][j]+e[all[j][i][1]][2]);
                    else 
                        ans=min(ans, sum+d[j][i]+c[i][j]+e[all[j][i][0]][2]);
*/
                    if(k==all[j][i][0])
                        ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][1]][2]);
                    else 
                        ans=min(ans, sum+d[i][j]+c[j][i]+e[all[j][i][0]][2]);

                }
            }            

        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            //blocklanan edge i ve j arasında

            if(d[n][i]==INF||c[n][j]==INF) continue;
            int sum=d[n][i]+c[n][j];

            for(auto k: all[j][i]){
                sum+=e[k][2];
                sum+=di[k];
                //cout<<j<<" "<<i<<"\n";
                ans=min(ans, sum+min((i==0)?INF:b[i][0], (j==0)?INF:b[j][0]));
                //j-> i di
                //i -> j yaptı

                if(all[j][i].size()>1){
                    if(k==all[j][i][0])
                        ans=min(ans, sum+b[j][i]+a[i][j]+e[all[j][i][1]][2]);
                    else 
                        ans=min(ans, sum+b[j][i]+a[i][j]+e[all[j][i][0]][2]);
                }
            }            

        }
    }
    ans = min(ans, a[n][n-1]+d[n][0]);
    if(ans==INF) cout<<-1;
    else cout<<ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 22 ms 2904 KB Output is correct
4 Correct 21 ms 2648 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8408 KB Output is correct
2 Incorrect 135 ms 8164 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2896 KB Output is correct
2 Correct 3 ms 2648 KB Output is correct
3 Correct 57 ms 7232 KB Output is correct
4 Correct 3 ms 2652 KB Output is correct
5 Correct 69 ms 8260 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 47 ms 8780 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 22 ms 2904 KB Output is correct
4 Correct 21 ms 2648 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Incorrect 1 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -