Submission #1144516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144516		tnt	Commuter Pass (JOI18_commuter_pass)	C++20	100 / 100	413 ms	33548 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#define pb push_back                    
#define ll long long
#define int long long
//#define sort(all(v)) sort(v.begin(),v.end())

int mod = 998244353;
const int N = 1e5 + 10;
const int inf = 1e9;
int fact[200001];
ll binpow(ll a, ll b){
 if(b == 0) return 1;
 else if(b % 2 == 1) return (a * binpow(a, b - 1)) % mod;
 ll p = binpow(a,b / 2);
 return (p * p) % mod;
}
vector<int> d(N,1e18),d1(N,1e18),d2(N,1e18),d3(N,1e18);
int was[N],dp[N][3];
vector <pair<int,int>> g[N];
vector <int> g1[N],top;
void dfs(int u){
    was[u] = 1;
    for(int to : g1[u]){
        if(was[to] != 0) continue;
        dfs(to);
    }
    top.pb(u);
}
signed main(){
    //freopen("mootube.in", "r", stdin);
    //freopen("mootube.out", "w", stdout);
    int n,m,s,t,u,v;
    cin >> n >> m >> s >> t >> u >> v;
    vector <array<int,3>> q;
    for(int i = 1; i <= m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        g[a].pb({b,c});
        g[b].pb({a,c});
        q.pb({a,b,c});
    }
    set <pair<int,int>> st;
    st.insert({0,s});
    d[s] = 0;
    while(st.size() > 0){
        int u1 = (*st.begin()).second;
        st.erase(st.begin());
        for(auto [to,w] : g[u1]){
            if(d[to] > d[u1] + w){
                st.erase({d[to],to});
                d[to] = d[u1] + w;
                st.insert({d[to],to});
            }
        }
    }
    st.insert({0,t});
    d1[t] = 0;
    while(st.size() > 0){
        int u1 = (*st.begin()).second;
        st.erase(st.begin());
        for(auto [to,w] : g[u1]){
            if(d1[to] > d1[u1] + w){
                st.erase({d1[to],to});
                d1[to] = d1[u1] + w;
                st.insert({d1[to],to});
            }
        }
    }
    st.insert({0,u});
    d2[u] = 0;
    while(st.size() > 0){
        int u1 = (*st.begin()).second;
        st.erase(st.begin());
        for(auto [to,w] : g[u1]){
            if(d2[to] > d2[u1] + w){
                st.erase({d2[to],to});
                d2[to] = d2[u1] + w;
                st.insert({d2[to],to});
            }
        }
    }
    st.insert({0,v});
    d3[v] = 0;
    while(st.size() > 0){
        int u1 = (*st.begin()).second;
        st.erase(st.begin());
        for(auto [to,w] : g[u1]){
            if(d3[to] > d3[u1] + w){
                st.erase({d3[to],to});
                d3[to] = d3[u1] + w;
                st.insert({d3[to],to});
            }
        }
    }
    for(int i = 0; i < m; i++){
        int a = q[i][0],b = q[i][1],c = q[i][2];
        if(d[a] + d1[b] + c == d[t]){
            g1[a].pb(b);
        }
        if(d[b] + d1[a] + c == d[t]){
            g1[b].pb(a);
        }
    }
    dfs(s);
    for(int i = 0; i < top.size(); i++){
        //cout << top[i] << ' ';
        dp[top[i]][1] = d3[top[i]];
        dp[top[i]][2] = d2[top[i]];
        for(auto to : g1[top[i]]){
            dp[top[i]][1] = min(dp[top[i]][1],dp[to][1]);
            dp[top[i]][2] = min(dp[top[i]][2],dp[to][2]);
            //cout << to << " ";
        }
    }
    int ans = d2[v];
    for(int i : top){
        ans = min({ans,d2[i] + dp[i][1],d3[i] + dp[i][2]});
        //cout << dp[i][1] << ' ' <<  dp[i][2] << " " << i <<  '\n';
    }
    cout << ans;
}

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