Submission #891459

#	Time	Username	Problem	Language	Result	Execution time	Memory
891459		hafo	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	52 ms	3852 KiB

ho_t4

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;
 
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
 
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 200 + 7;
const ll oo = 1e15 + 69;
const int maxe = 5e4 + 7;
 
int n, m;
pa trace[maxn][maxn];
ll c[maxn][maxn], c2[maxn][maxn], best_without_u[maxe];
struct edge {
    int u, v, c, d;
} ed[maxe];
bool used[maxe];
 
void solve(int s, int t) {
    vector<pa> path;
    fill_n(used, m + 1, 0);
 
    int p = s;
    while(p != t) {
        path.pb({p, trace[p][t].se});
        used[trace[p][t].se] = 1;
        p = trace[p][t].fi;
    }
    path.pb({t, 0});
    
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) c2[i][j] = (i == j ? 0:oo);
    }
    
    for(int i = 1; i <= m; i++) {
        if(used[i]) continue;
        int u = ed[i].u, v = ed[i].v;
        best_without_u[i] += min(c[s][v] + c[u][t] + ed[i].c, c[s][t]);
        mini(c2[ed[i].u][ed[i].v], ed[i].c);
    }
 
    for(int k = 1; k <= n; k++) {
        for(int u = 1; u <= n; u++) {
            for(int v = 1; v <= n; v++) mini(c2[u][v], c2[u][k] + c2[k][v]);
        }
    }
 
    for(int i = 0; i < Size(path) - 1; i++) {
        ll mn = oo;
        for(int j = 0; j <= i; j++) {
            for(int k = i + 1; k < Size(path); k++) {
                int u = path[j].fi;
                int v = path[k].fi;
                mini(mn, c[s][u] + c2[u][v] + c[v][t]);
            }
        }
        best_without_u[path[i].se] += mn;
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);
 
    cin>>n>>m;
    for(int i = 1; i <= m; i++) {
        cin>>ed[i].u>>ed[i].v>>ed[i].c>>ed[i].d;
    }
 
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            c[i][j] = (i == j ? 0:oo);
            trace[i][j] = {j, 0};
        }
    }
 
    for(int i = 1; i <= m; i++) {
        if(mini(c[ed[i].u][ed[i].v], ed[i].c)) trace[ed[i].u][ed[i].v].se = i;
    }
    for(int k = 1; k <= n; k++) {
        for(int u = 1; u <= n; u++) {
            for(int v = 1; v <= n; v++) {
                if(mini(c[u][v], c[u][k] + c[k][v])) trace[u][v] = trace[u][k];
            }
        }
    }
 
    ll ans = oo;
    mini(ans, c[1][n] + c[n][1]);
    solve(1, n);
    solve(n, 1);

    for(int i = 1; i <= m; i++) {
        mini(ans, best_without_u[i] + ed[i].d);
    }
    cout<<(ans == oo ? -1:ans);
    return 0;
}

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