Submission #541134

#	Time	Username	Problem	Language	Result	Execution time	Memory
541134		PixelCat	Olympic Bus (JOI20_ho_t4)	C++14	100 / 100	600 ms	4228 KiB

ho_t4

/* code by the cute ~~Dengdualang~~ PixelCat owo */
/*     as cute as nacho neko (aka. my wife)!     */

/*     Nhade stay for a night here               */
/*     183234 deng deng deng pixelcat oops       */
/*     (yang wang yesu)*2                        */
/*     ^ some weird stuff. nvm =w=               */

#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using LLL = __int128_t;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(998244353)
// #define MOD (int)((LL)1e9 + 7)
#define INF (int)(4e18)
// #define INF 1e9
#define EPS (1e-6)

#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p >>= 1;
        b = b * b % mod;
    }
    return ans;
}
int fpow(int b, int p) {
    return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

struct Edge{
    int s,t,c,d;
}ed[50050];
int tag[50050];

vector<int> adj[210];
int ad[210][210];

int dist[210];
int src[210];
int dijk(int s,int t,int nope,int tg){
    // debug(s,t);

    if(nope>0){
        ed[0]=ed[nope];
        swap(ed[0].s,ed[0].t);
        adj[ed[0].s].eb(0);
    }

    memset(dist,0x3f3f3f3f,sizeof(dist));
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.emplace(0,s);
    dist[s]=0;
    while(!pq.empty()){
        int d=pq.top().F;
        int now=pq.top().S;
        pq.pop();
        if(dist[now]<d) continue;
        for(auto &eid:adj[now]) if(eid!=nope){
            auto &e=ed[eid];
            if(dist[e.t]>d+e.c){
                dist[e.t]=d+e.c;
                pq.emplace(d+e.c,e.t);
                src[e.t]=eid;
            }
        }
    }
    if(nope>0){
        adj[ed[0].s].pop_back();
    }

    if(dist[t]>=INF) return INF;

    if(tg){
        int now=t;
        while(now!=s){
            tag[src[now]]^=tg;
            now=ed[src[now]].s;
        }
    }

    return dist[t];
}

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    int n,m; cin>>n>>m;
    memset(ad,0x3f3f3f3f,sizeof(ad));
    For(i,1,n) ad[i][i]=0;
    For(i,1,m){
        auto &e=ed[i];
        cin>>e.s>>e.t>>e.c>>e.d;
        adj[e.s].eb(i);
        chmin(ad[e.s][e.t],e.c);
    }
    For(k,1,n) For(i,1,n) For(j,1,n){
        chmin(ad[i][j],ad[i][k]+ad[k][j]);
    }
    int m1n=dijk(1,n,-1,1);
    int mn1=dijk(n,1,-1,2);
    int ans=m1n+mn1;
    For(eid,1,m){
        auto &e=ed[eid];
        int d1n,dn1;
        if(tag[eid]&1) d1n=dijk(1,n,eid,0);
        else d1n=min(m1n,ad[1][e.t]+ad[e.s][n]+e.c);
        if(tag[eid]&2) dn1=dijk(n,1,eid,0);
        else dn1=min(mn1,ad[n][e.t]+ad[e.s][1]+e.c);
        chmin(ans,d1n+dn1+e.d);
        // debug(eid,d1n,dn1);
    }
    if(ans>=INF) cout<<"-1\n";
    else cout<<ans<<"\n";
    return 0;
}

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