Submission #891242

#	Time	Username	Problem	Language	Result	Execution time	Memory
891242		hafo	Olympic Bus (JOI20_ho_t4)	C++14	11 / 100	50 ms	3832 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 = 1e18 + 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];

ll solve(int s, int t) {
    vector<pa> path;
    for(int i = 1; i <= m; i++) {
        best_without_u[i] = oo;
        used[i] = 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++) {
        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(best_without_u[path[i].se], c[s][u] + c2[u][v] + c[v][t]);
            }
        }
    }

    ll ans = oo;
    for(int i = 1; i <= m; i++) {
        int u = ed[i].u, v = ed[i].v;
        mini(ans, best_without_u[i] + c[t][v] + c[u][s] + ed[i].c + ed[i].d);
    }
    return ans;
}

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]);
    mini(ans, solve(1, n)); 
    mini(ans, solve(n, 1)); 

    cout<<(ans == oo ? -1:ans);
    return 0;
}

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