제출 #494064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
494064		balbit	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	406 ms	4904 KiB

ho_t4

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#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 NN = 2e2+5;
const int MM = 5e4+5;

int w[NN][NN];
int who[NN][NN];
int from[NN];
int treeedge[MM];
bool done[NN];
ll dst[NN];
ll SD[NN], TD[NN]; // distances from the start and end, respectively
ll TMP[NN];
struct edge{
    int u, v, w, fost, id; // fost = flipping cost
};
edge E[MM];
int n,m;

ll dij(/*vector<edge> &edges, */ll *d, int S, int T, bool tree) {
    memset(w, 0x3f, sizeof w);

    bug("yart");

    REP(i,m) {
        edge e = E[i];
        if (w[e.u][e.v] > e.w) {
            w[e.u][e.v] = e.w;
            who[e.u][e.v] = e.id;
        }
    }
    memset(done, 0, sizeof done);
    memset(d, 0x3f, sizeof SD);
    d[S] = 0;
    while (1) {
        int v = -1; ll bad = 0x3f3f3f3f3f3f3f3f;
        REP(i,n) {
            if (!done[i] && d[i] < bad) {
                bad = d[i]; v = i;
            }
        }
        if(v == -1) break;
        done[v] = 1;
        REP(u, n) {
            if (!done[u] && d[u] > d[v] + w[v][u]) {
                d[u] = d[v] + w[v][u];
                from[u] = v;
            }
        }
    }
    if (tree) {
        REP(i,n) {
            if (done[i] && i != S) {
                int f = from[i];
                treeedge[who[f][i]] = 1;
                bug("Tree!", who[f][i], E[who[f][i]].u, E[who[f][i]].v);
            }
        }
    }
    return d[T];
}

ll floy[NN][NN];

signed main(){
    IOS();
    cin>>n>>m;
    memset(floy, 0x3f, sizeof floy);
    REP(i,m) {
        cin>>E[i].u>>E[i].v>>E[i].w>>E[i].fost; --E[i].u; --E[i].v;
        E[i].id = i;
        MN(floy[E[i].u][E[i].v], E[i].w);
    }
    REP(i,n) floy[i][i] = 0;

    REP(k,n) REP(i,n) REP(j,n) {
        MN(floy[i][j], floy[i][k] + floy[k][j]);
    }

    ll ftrip = dij(SD, 0, n-1, 1);

    ll btrip = dij(TD, n-1, 0, 1);

    ll re = ftrip + btrip;

    bug(re);

    REP(i,m) {
        // try flipping this bit
        bug(i, treeedge[i]);
        if (treeedge[i]) {
            // ok, just brute it
            swap(E[i].u, E[i].v);
            ll go = dij(TMP, 0, n-1, 0);
            ll bk = dij(TMP, n-1, 0, 0);
            bug(go, bk);
            MN(re, go+bk+E[i].fost);
            swap(E[i].u, E[i].v);
        }else{
            int u = E[i].u, v = E[i].v;
            ll newf;

            if (SD[v] == inf) newf = ftrip;
            else newf = SD[v] + floy[u][n-1] + E[i].w;

            ll newb;
            if (TD[v] == inf) newb = btrip;
            else newb = TD[v] + floy[u][0] + E[i].w;
            MN(newf, ftrip); MN(newb, btrip);
            bug(newf, newb);
            MN(re, newf + newb + E[i].fost);
        }
    }
    if (re >= inf-10) re = -1;
    cout<<re<<endl;



}

/*

// fear: what if T cannot be reached by v?????

2 2
1 2 7 3
1 2 4 8
*/

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