Submission #975027

#	Time	Username	Problem	Language	Result	Execution time	Memory
975027		berr	Olympic Bus (JOI20_ho_t4)	C++17	37 / 100	1035 ms	9728 KiB

ho_t4

#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&&geey){
        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]: geey[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(i==j) continue;

            if(a[j][i]==INF||b[i][j]==INF) continue;
            int sum=a[j][i]+b[i][j];
            int tsum=sum;
            for(auto k: all[j][i]){
                sum=tsum;
                sum+=e[k][2];
                sum+=di[k];
                if(all[j][i].size()>1){
                 
                    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 g=0; g<n; g++){
                    if(g!=i&&g!=j){
                        ans=min(ans, sum+d[j][g]+c[i][g]);
                        ans=min(ans, sum+d[i][g]+c[j][g]);
                    }
                }

                ans=min(ans, sum+c[i][j]+d[j][i]+e[k][2]);
                // diğer değer

                if(all[i][j].size()>0){
                    ans=min(ans, sum+c[i][j]+d[j][i]+e[all[i][j][0]][2]);
                }
            }            

        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            //blocklanan edge i ve j arasında
            if(i==j) continue;
            if(d[j][i]==INF||c[i][j]==INF) continue;
            int sum=d[j][i]+c[i][j];
          //  cout<<i<<" "<<j<<"\n";
            //cout<<d[n][i]<<" "<<c[n][j]<<"\n";
            int tsum=sum;
            for(auto k: all[j][i]){
                sum=tsum;
                sum+=e[k][2];
                sum+=di[k];


                //cout<<j<<" "<<i<<"\n";

                //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]);
                }


                for(int g=0; g<n; g++){
                    if(g!=i&&g!=j){
                        ans=min(ans, sum+b[j][g]+a[i][g]);
                        ans=min(ans, sum+b[i][g]+a[j][g]);
                    }
                
                }

                //cout<<j<<" "<<i<<"\n";

                ans=min(ans, sum+a[j][i]+b[i][j]+e[k][2]);
                // diğer değer

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

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

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 21 / 21
• Subtask 4: 0 / 63