Submission #197094

#	Time	Username	Problem	Language	Result	Execution time	Memory
197094		quocnguyen1012	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	617 ms	23532 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i=(n-1); i>=0; --i)
#define REP1(i,n) FOR(i,1,n+1)
#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 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 = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;
 
 
void GG(){cout<<"-1\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;
}
 
const int maxn = 1e5+5;
 
vector<pii> g[maxn]; // to, weight. 1-based
ll ds[maxn], dt[maxn], du[maxn], dv[maxn];
 
void dij(ll d[], int S){
    priority_queue<pii, vector<pii>, greater<pii> > pq; // Distance, node
    fill(d, d+maxn, inf);
    d[S]=0; pq.push({0,S});
    while (!pq.empty()) {
        ll w = pq.top().f, v = pq.top().s;
        pq.pop();
        if (w != d[v]) {
            continue;
        }
        for (pii &e : g[v]) {
            if (d[e.f] > d[v] + e.s) {
                d[e.f] = d[v] + e.s;
                pq.push({d[e.f],e.f});
            }
        }
    }
}
 
bool B[maxn]; // black
ll mnu[maxn]; // Min distance to u walking on s-t shortest path
signed main(){
    IOS();
    int n, m; cin>>n>>m;
    int s,t,u,v;
    cin>>s>>t>>u>>v;
    REP(i,m) {
        int a, b, c; cin>>a>>b>>c;
        g[a].pb({b,c});
        g[b].pb({a,c});
    }
    dij(ds,s);
    REP1(i,n) {
        bug(i, ds[i]);
    }
    dij(dt,t);
    dij(dv,v);
    dij(du,u);
        ll re = inf;
    ll tg = ds[t]; assert(tg == dt[s]);
    {
        vector<int> q;
        fill(mnu, mnu+maxn, inf);
        static int seen[maxn];
        seen[s]=1;
        REP1(i,n) q.pb(i);
        sort(ALL(q), [](int a, int b){return ds[a]<ds[b];});
        REP(i,n) {
            int at = q[i];
            MN(mnu[at], du[at]);
            for (pii &e : g[at]) {
                int to = e.f;
                if (ds[at] + e.s + dt[to] == ds[t]) {
                    MN(mnu[to], mnu[at]);
                }
            }
            bug(at,mnu[at],dv[at]);
            MN(re, mnu[at] + dv[at]);
        }
    }
 
    {
        swap(s,t); swap(ds,dt);
        vector<int> q;
        fill(mnu, mnu+maxn, inf);
        static int seen[maxn];
        seen[s]=1;
        REP1(i,n) q.pb(i);
        sort(ALL(q), [](int a, int b){return ds[a]<ds[b];});
        REP(i,n) {
            int at = q[i];
            MN(mnu[at], du[at]);
            for (pii &e : g[at]) {
                int to = e.f;
                if (ds[at] + e.s + dt[to] == ds[t]) {
                    MN(mnu[to], mnu[at]);
                }
            }
            bug(at,mnu[at],dv[at]);
            MN(re, mnu[at] + dv[at]);
        }
    }
    cout<<min(re, du[v])<<endl;
 
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:100:20: warning: variable 'seen' set but not used [-Wunused-but-set-variable]
         static int seen[maxn];
                    ^~~~
commuter_pass.cpp:122:20: warning: variable 'seen' set but not used [-Wunused-but-set-variable]
         static int seen[maxn];
                    ^~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45