Submission #1161044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161044		sitablechair	Olympic Bus (JOI20_ho_t4)	C++20	11 / 100	34 ms	2628 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],tp;
ll ans[50003],dp1[N],dp2[N];

void dfs(int u) {
    for(auto i: g[u])
        if (!vs[e[i].v]) {
            vs[e[i].v]=1;
            dfs(e[i].v);
        }
    tp.pb(u);
}

void solve(int s,int t) {
    For(i,1,n) g[i].clear();
    fill(c+1,c+1+m,0);
    fill(vs+1,vs+1+n,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);
    tp.clear();
    For(i,1,n)
        if (!vs[i]) dfs(i);
    fill(dp1,dp1+1+n,0);
    fill(dp2,dp2+1+n,0);
    dp1[s]=1;
    dp2[t]=1;
    reverse(all(tp));
    for(auto u: tp) 
        for(auto i: g[u]) {
            int v=e[i].v;
            dp1[v]=(dp1[v]+dp1[u])%MOD;
        }
    ForD(j,sz(tp)-1,0) {
        int u=tp[j];
        for(auto i: g[u]) {
            int v=e[i].v;
            dp2[u]=(dp2[u]+dp2[v])%MOD;
        }
    }
    For(i,1,n)
        for(auto el: g[i]) {
            int u=e[el].u,v=e[el].v;
            ll kk=1LL*dp1[u]*dp2[v]%MOD;
            kk=(kk-dp1[t])%MOD;
            if (kk==0) c[el]=1;
        }
    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: 0 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 63