Submission #1161055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161055		sitablechair	Olympic Bus (JOI20_ho_t4)	C++20	16 / 100	1095 ms	2120 KiB

ho_t4

#include <bits/stdc++.h>

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else 
#define debug(...) "fr";
#endif

using namespace std;

const int MOD=1e9+7,N=203;

struct Edge {
    int u,v,w,d;
};

int n,m;
ll f[N][N],f1[N][N];
Edge e[50003];
bool c[50003],vs[N];
vector<int> g[N],g1[N];
ll ans[50003];

void dfs(int u,int idx) {
    vs[u]=1;
    for(auto i: g[u]) {
        if (i==idx) continue;
        int v=e[i].v;
        if (!vs[v]) dfs(v,idx);
    }
}
void solve(int s,int t) {
    For(i,1,n) g[i].clear();
    fill(c+1,c+1+m,0);
    For(i,1,m)
        if (f[s][e[i].u]+f[e[i].v][t]+e[i].w==f[s][t]) g[e[i].u].pb(i);

    For(i,1,m) 
        if (f[s][e[i].u]+f[e[i].v][t]+e[i].w==f[s][t]) {
            fill(vs,vs+1+n,0);
            dfs(s,i);
            c[i]=!(vs[t]);
        }
    For(i,1,n) {
        For(j,1,n) 
            f1[i][j]=1e17;
        f1[i][i]=0;
    }    
    For(i,1,m)
        if (!c[i]) f1[e[i].u][e[i].v]=min(f1[e[i].u][e[i].v],(ll)e[i].w);
    For(k,1,n)
        For(i,1,n)
            For(j,1,n) f1[i][j]=min(f1[i][j],f1[i][k]+f1[k][j]); 
    int sigma=0;
    For(i,1,m) sigma+=c[i];
    assert(sigma<=n);
    For(i,1,m) {
        ll tmp=1e18;
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if (f[s][u]>f[s][v]) {
            tmp=f[s][v]+w+f[u][t];  
        }
        if (c[i]) {
            For(j,1,n)
                For(k,1,n) {
                    if (f[s][u]+f[v][j]+w!=f[s][j] && f[k][u]+w+f[v][t]!=f[k][t]) 
                        tmp=min(tmp,f[s][j]+f[k][t]+f1[j][k]);     
                }
        } else tmp=min(tmp,f[s][t]);
        ans[i]+=tmp;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m;
    For(i,1,m) {
        cin >> e[i].u >> e[i].v >> e[i].w >> e[i].d;
       
    } 
    For(i,1,n) {
        For(j,1,n) 
            f[i][j]=f1[i][j]=1e17;
        f[i][i]=f1[i][i]=0;
    }
    For(i,1,m) f[e[i].u][e[i].v]=min(f[e[i].u][e[i].v],(ll)e[i].w);
    For(k,1,n)
        For(i,1,n)
            For(j,1,n) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); 
   
    ll res=1e18;
    solve(1,n);
    solve(n,1);
    For(i,1,m)  
        res=min(res,ans[i]+e[i].d);
    res=min(res,f[1][n]+f[n][1]);
    if (res>=1e16) cout << -1 << endl;
    else cout << res << endl;
    return 0;
}

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