Submission #946810

#	Time	Username	Problem	Language	Result	Execution time	Memory
946810		vjudge1	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	248 ms	30108 KiB

commuter_pass

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
#define ll long long
#define int long long
#define all(v) v.begin(), v.end()
#define nl '\n'
#define pb push_back
#define sz(s) (int)(s).size()
#define f first
#define s second
using namespace std;
const ll N = 1e5 + 50, MX = 1e18;
bool was[N], grd[N], use[N], had[N];
ll du[N], dv[N], ds[N], dt[N];
vector <pair <int, int> > g[N], Q[N];
vector <int> top;
ll dp[N][2];
ll n;
ll s, t, u, v;
void dfs(ll curv){
    use[curv]=1;
    for(auto [x,w]:g[curv]){
        if(!use[x])dfs(x);
    }
    if(grd[curv])top.pb(curv);
}
void filv(){
    for (int i = 1; i <= n; i++) {
        was[i]=0;
        //dv[i]=MX;
    }
    dv[v]=0;
    priority_queue< pair<long long, int> > st;
    st.push({0, v});
    while(st.size() != 0) {
        int curv = st.top().second;
        st.pop();
        if(was[curv]) continue;
        was[curv] = 1;
        for(auto [to, w]: g[curv]) {
            if(dv[to] > dv[curv] + w) {
                //s.erase({d[to], to});
                dv[to] = dv[curv] + w;
                st.push({-dv[to], to});
            }
        }
    }
}
void filu(){
    for (int i = 1; i <= n; i++) {
        was[i]=0;
        //du[i]=MX;
    }
    du[u]=0;
    priority_queue< pair<long long, int> > st;
    st.push({0, u});
    while(st.size() != 0) {
        int curv = st.top().second;
        st.pop();
        if(was[curv]) continue;
        was[curv] = 1;
        for(auto [to, w]: g[curv]) {
            if(du[to] > du[curv] + w) {
                //s.erase({d[to], to});
                du[to] = du[curv] + w;
                st.push({-du[to], to});
            }
        }
    }
}
void fils(){
    for (int i = 1; i <= n; i++) {
        was[i]=0;
        //ds[i]=MX;
    }
    ds[s]=0;
    priority_queue< pair<long long, int> > st;
    st.push({0, s});
    while(st.size() != 0) {
        int curv = st.top().second;
        st.pop();
        if(was[curv]) continue;
        was[curv] = 1;
        for(auto [to, w]: g[curv]) {
            if(ds[to] > ds[curv] + w) {
                //s.erase({d[to], to});
                ds[to] = ds[curv] + w;
                st.push({-ds[to], to});
            }
        }
    }
}
void filt(){
    for (int i = 1; i <= n; i++) {
        was[i]=0;
        dp[i][0]=dp[i][1]=MX;
        //dt[i]=MX;
    }
    dt[t]=0;
    priority_queue< pair<long long, int> > st;
    st.push({0, t});
    while(st.size() != 0) {
        int curv = st.top().second;
        st.pop();
        if(was[curv]) continue;
        was[curv] = 1;
        for(auto [to, w]: g[curv]) {
            if(dt[to] > dt[curv] + w) {
                //s.erase({d[to], to});
                dt[to] = dt[curv] + w;
                st.push({-dt[to], to});
            }
        }
    }
}
void solve(){
    ll m;
    cin >> n >> m;
    cin >> s >> t >> u >> v;
    for(int i = 1; i <= m; i++){
        ll a, b, x;
        cin >> a >> b >> x;
        g[a].pb({b,x});
        g[b].pb({a, x});
    }
    for(int i = 1; i <= n; i++){
        dt[i] = ds[i] = du[i] = dv[i] = MX;
    }
    filt(), filu(), filv(), fils();
    for(int i = 1; i <= n; i++){
        if(ds[i] + dt[i] == ds[t]){
            grd[i]=1;
            //cout << i << nl;
        }
    }
    for(int i = 1; i <= n; i++){
        if(grd[i]) {
            for (auto [x,w]: g[i]) {
                if (dt[x] + w + ds[i] == ds[t]) {
                    Q[i].pb({x, w});
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        g[i].clear();
    }
    for(int i = 1; i <= n; i++){
        for(auto [x, w]: Q[i]){
            g[i].pb({x, 0});
        }
    }
    for(int i = 1; i <= n; i++){
        for(auto [x, w]: g[i]){
            //cout << i << " " << x << " " << w << nl;
        }
    }
    for(int i = 1; i <= n; i++){
        if(!use[i] && grd[i])dfs(i);
    }
    for(auto x:top){
        dp[x][0] = du[x];
        dp[x][1] = dv[x];
        for (auto [to, w]: g[x]) {
            dp[x][0] = min(dp[x][0], dp[to][0]);
            dp[x][1] = min(dp[x][1], dp[to][1]);
        }
    }
    ll mn = du[v];
    for(auto x: top){
        mn = min(mn, dp[x][0] + dv[x]);
        mn = min(mn, dp[x][1] + du[x]);
    }
    cout << mn;
}
signed main(){
    //freopen("lca.in", "r", stdin);
    //freopen("lca.out", "w", stdout);
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll ql=1;
    //cin >> ql;
    //tst++;
    while(ql--){
        solve();
    }
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void solve()':
commuter_pass.cpp:181:18: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  181 |         for(auto [x, w]: g[i]){
      |                  ^~~~~~

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