Submission #366769

#	Time	Username	Problem	Language	Result	Execution time	Memory
366769		balbit	Olympic Bus (JOI20_ho_t4)	C++14	0 / 100	35 ms	9468 KiB

ho_t4

#include <bits/stdc++.h>
//#undef BALBIT
using namespace std;
#define ll long long
#define int ll
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 200+5;

struct edge{
    int v, u, w, d, i;
};

vector<edge> g[maxn], gt[maxn];
bool done[maxn], ban[maxn*maxn];
int par[maxn];
ll d[maxn], rd[maxn];
int n,m;

ll dij(int S, int T, vector<edge> gee[], ll D[]){
//    return 3;
    assert(D[17] == 0x3f3f3f3f3f3f3f3f);
    memset (done, 0, sizeof done);
    D[S] = 0;
    while (1){
        ll w = inf; int v = -1;
        REP(i,n) {
            if (!done[i]) {
                if (D[i] < w) {
                    w = D[i]; v = i;
                }
            }
        }
        if (v == -1) break;
        done[v] = 1;
        for (edge & e : gee[v]) {
            if (e.i!=-1 && ban[e.i]) continue;
            if (D[e.u] > D[v] + e.w) {
                D[e.u] = D[v] + e.w;
                par[e.u] = e.i;
            }
        }
    }
    return D[T];
}

vector<edge> E;

ll go(int S = 0, int T = n-1) {
//    return -1;
    memset(ban, 0, sizeof ban);
    memset(par, -1, sizeof par);
    memset (d, 0x3f, sizeof d);
    ll re = dij(T, S, g, d);
    memset (d, 0x3f, sizeof d);
    ll straight = dij(S,T, g, d);
    re += straight; MN(re, inf);
    vector<int> pth;
    if (straight < inf){
        for (int at = T; par[at] !=-1 && at != S; ) {
            bug(par[at]);
            pth.pb(par[at]);
            ban[par[at]] = 1;
            at = E[par[at]].v;
        }
    }
//    return -1;
    bug(straight);
    memset (d, 0x3f, sizeof d);
    memset (rd, 0x3f, sizeof rd);
    dij(T, S, g, d);
    dij(S, T, gt,rd);
    for (edge &e : E) {
        if (!ban[e.i]) {
            MN(re, straight + min(inf, rd[e.v] + d[e.u]) + e.d + e.w);
//            if (e.i == 1) {
//                bug(e.v, e.u, rd[e.v]+ d[e.u]+ e.d+ e.w + straight);
//            }
        }
//        bug(re);
    }
    memset(ban, 0, sizeof ban);
    for (int i : pth) {
        edge & e = E[i];
        ban[e.i] = 1; g[e.u].pb({e.u, e.v, e.w, e.d, -1});
        memset (d, 0x3f, sizeof d);
        ll t1 = dij(S,T,g,d);
        memset (d, 0x3f, sizeof d);
        ll t2 = dij(T,S,g,d);
        MN(re, t1+t2);
        g[e.u].pop_back();
        ban[e.i] = 0;
    }
    return re;
}

signed main(){
    IOS();
    cin>>n>>m;
    REP(i,m) {
        int a,b,w,p; cin>>a>>b>>w>>p; --a; --b;
        E.pb({a,b,w,p,i});
        g[a] .pb({a,b,w,p,i});
        gt[b].pb({b,a,w,p,i});
    }
    ll ans = go();
    bug(ans);
//    swap(g, gt);
//    for (edge & e : E) swap(e.v, e.u);
    ans = min(ans, go(n-1, 0));
    bug(ans);
    if (ans > inf/2) ans = -1;
    cout<<ans<<endl;

}

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