Submission #975041

#	Time	Username	Problem	Language	Result	Execution time	Memory
975041		berr	Olympic Bus (JOI20_ho_t4)	C++17	100 / 100	934 ms	11980 KiB

ho_t4

#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int N=205, INF=1e16;
vector<int> all[N][N], all2[N][N];
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));
 


void dijkstra(int v, int skip, vector<int> &dist, vector<vector<array<int, 3>>> &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});
            }
        }
    }
}
 
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);
 
    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);
        all2[u][v].push_back(cnt);
        cnt++;
    }


    for(int i=0; i<n; i++){

        sort(g[i].begin(), g[i].end(), [&](auto x, auto y){
            return x[1] < y[1];
        });
        sort(g_rev[i].begin(), g_rev[i].end(), [&](auto x, auto y){
            return x[1] < y[1];
        });

        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];
            });
            sort(all2[i][l].begin(), all2[i][l].end(), [&](int x, int y){
                return e[x][2]+di[x] < e[y][2]+di[y];
            });
        }
    }
 
    // a = 1 -> i, b = i -> n
    // c = i -> 1 without x
    // d = n -> i without x
 
    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, ksum=INF;
            int g=0;
            for(auto k: all2[j][i]){
                g++;
                if(g==4) break;
                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]);
 
                }
 
                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]);
                }
                ksum=min(ksum, sum);

            }   

            for(int g=0; g<n; g++){
                if(g!=i&&g!=j){
                    ans=min(ans, ksum+d[j][g]+c[i][g]);
                    ans=min(ans, ksum+d[i][g]+c[j][g]);
                }
            }         

        }
    }
 
    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, ksum=INF;;
            int g=0;
            for(auto k: all2[j][i]){
                g++;
                if(g==3) break;
                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]);
                }
                //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]);
                }
                ksum=min(ksum, sum);
 
            }
            for(int g=0; g<n; g++){
                if(g!=i&&g!=j){
                    ans=min(ans, ksum+b[j][g]+a[i][g]);
                    ans=min(ans, ksum+b[i][g]+a[j][g]);
                }
            }
        }
    }
    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: 63 / 63