Submission #1139000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139000		kitkat12	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	323 ms	37008 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int (i) = (a); (i) < (b); (i)++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define min(a,b) (a<=b ? a : b)
#define max(a,b) (a>=b ? a : b)
//using u64 = uint64_t;
//using u128 = __uint128_t;

const int nmax = 1e5+3;
const ll inf = 1e18;
vector<pii> adj[nmax];
vector<int> bes[nmax], invbes[nmax];
bool vis[nmax],best[nmax];

void dijk(vector<ll> &d, int s){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    d[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        const auto [d_v, v] = pq.top();
        pq.pop();
        if(d_v!=d[v]) continue;
        for(const auto [to, len] : adj[v]){
            if(d_v+len<d[to]){
                d[to] = d_v+len;
                pq.push({d[to],to});
            }
        }
    }
}

void dijk2(vector<ll> &d, int s){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    d[s]=0;
    pq.push({0,s});
    while(!pq.empty()){
        const auto [d_v, v] = pq.top();
        pq.pop();
        if(d_v!=d[v] || best[v]) continue;
        for(const auto [to, len] : adj[v]){
            if(d_v+len<d[to]){
                d[to] = d_v+len;
                pq.push({d[to],to});
            }
        }
    }
}

void dfs(int u, vector<ll> &d){
    vis[u] = 1;
    for(const auto [to, len]:adj[u]){
        if(d[to]+len==d[u]){
            best[to]=1;
            bes[u].pb(to);
            invbes[to].pb(u);
        }
        if(!vis[to])dfs(to,d);
    }
}

void topodfs(int u, vector<int> &po, vector<int> graph[]){
    vis[u] = 1;
    for(int v:graph[u]){
        if(!vis[v])topodfs(v,po,graph);
    }
    po.pb(u);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m,s,t,u,v,a,b,c;
    cin>>n>>m>>s>>t>>u>>v;
    li(i,0,m){
        cin>>a>>b>>c;
        adj[a].pb({b,c});
        adj[b].pb({a,c});
    }
    vector<ll> ds(nmax, inf), du(nmax, inf), dv(nmax, inf), minv(nmax, inf), dp1(nmax,inf), dp2(nmax, inf);
    dijk(ds,s);
    mem(vis,0); mem(best,0);
    best[t]=1;
    dfs(t,ds);

    dijk(du,u);
    dijk(dv,v);

    //topo sort 
    vector<int> ts;
    mem(vis,0);
    topodfs(t,ts,bes);
    reverse(all(ts));
    for(int g : ts){
        dp1[g] = dv[g];
        for(int gk : invbes[g]){
            dp1[g] = min(dp1[g], dp1[gk]);
        }
    }

    vector<int> ts2;
    mem(vis,0);
    topodfs(s,ts2,invbes);
    reverse(all(ts2));
    for(int g : ts2){
        dp2[g] = dv[g];
        for(int gk : bes[g]){
            dp2[g] = min(dp2[g], dp2[gk]);
        }
    }

    // end game
    ll res = dv[u];
    for(int g : ts){
        res = min(res, du[g] + min(dp1[g],dp2[g])); 
    }
    cout<<res;

    return 0;
}

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