Submission #895889

#	Time	Username	Problem	Language	Result	Execution time	Memory
895889		niter	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	264 ms	32464 KiB

commuter_pass

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
//#define op(x) cerr << #x << " = " << x << endl;
//#define opa(x) cerr << #x << " = " << x << ", ";
//#define ops(x) cerr << x;
//#define entr cerr << endl;
//#define spac cerr << ' ';
//#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
//#define ARR(x, nnn) cerr << #x <<  " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) x.begin(), x.end()
#define unilize(x) x.resize(unique(BAE(x)) - x.begin())
#define unisort(x) sort(BAE(x)); unilize(x);
using namespace std;
typedef long long ll;

const int mxn = (int)(1e5) + 10;
const ll INF = 1e18;
struct EDGE{ int u, w; };
struct three_edge{ int ff, ss, w; };
vector<EDGE> E[mxn], F[mxn], G[mxn];
ll dp[mxn], d1[mxn], d2[mxn];
vector<three_edge> EV;
bool vis[mxn], n_vis[mxn];

void dfs(int v){
    vis[v] = true;
    for(auto &i:F[v]){
        if(!vis[i.u]){
            dfs(i.u);
        }
    }
}
void n_dfs(int v){
    n_vis[v] = true;
    for(auto &i:G[v]){
        if(!n_vis[i.u]){
            n_dfs(i.u);
        }
    }
}

int main(){
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m, S, T, U, V;
    cin >> n >> m >> S >> T >> U >> V;
    loop(i,0,m){
        int ia, ib, w;
        cin >> ia >> ib >> w;
        E[ia].pb({ib, w});
        E[ib].pb({ia, w});
        EV.pb({ia, ib, w});
    }
    loop(i,1,n+1) dp[i] = INF; dp[S] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    pq.push({0, S});
    while(!pq.empty()){
        int now = pq.top().ss;
        ll dis = pq.top().ff;
        pq.pop();
        if(dis != dp[now]) continue;
        for(auto &i:E[now]){
            if(dis + i.w < dp[i.u]){
                dp[i.u] = dis + i.w;
                pq.push({dp[i.u], i.u});
            }
        }
    }
    for(auto &i:EV){
        if(min(dp[i.ff], dp[i.ss]) + i.w == max(dp[i.ff], dp[i.ss])){
            int near = (dp[i.ff] < dp[i.ss]) ? i.ff : i.ss;
            int far = i.ff + i.ss - near;
            F[near].pb({far, 0});
//            opa(far) op(near)
//            opa(near) op(far)
            G[far].pb({near, 0});
        }
    }
    dfs(S);
    n_dfs(T);
    loop(i,1,n+1){
        F[i].clear();
        G[i].clear();
    }
    for(auto &i:EV){
        if(min(dp[i.ff], dp[i.ss]) + i.w == max(dp[i.ff], dp[i.ss])
           && vis[i.ff] && vis[i.ss] && n_vis[i.ff] && n_vis[i.ss]){
            int near = (dp[i.ff] < dp[i.ss]) ? i.ff : i.ss;
            int far = i.ff + i.ss - near;
            F[near].pb({far, 0});
            G[far].pb({near, 0});
        }
    }
    loop(i,1,n+1) dp[i] = INF; dp[U] = 0;
    pq.push({0, U});
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != dp[now]) continue;
        for(auto &i:E[now]){
            if(dp[i.u] > nd + i.w){
                dp[i.u] = nd + i.w;
                pq.push({dp[i.u], i.u});
            }
        }
    }
    ll ans = dp[V];
    loop(i,1,n+1){
        d1[i] = dp[i];
        pq.push({d1[i], i});
    }
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != d1[now]) continue;
        for(auto &i:F[now]){
            if(d1[i.u] > nd + i.w){
                d1[i.u] = nd + i.w;
                pq.push({d1[i.u], i.u});
            }
        }
    }
    loop(i,1,n+1){
        d2[i] = dp[i];
        pq.push({d2[i], i});
    }
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != d2[now]) continue;
        for(auto &i:G[now]){
            if(d2[i.u] > nd + i.w){
                d2[i.u] = nd + i.w;
                pq.push({d2[i.u], i.u});
            }
        }
    }
    loop(i,1,n+1){
        dp[i] = min(d1[i], d2[i]);
        pq.push({dp[i], i});
    }
    while(!pq.empty()){
        int now = pq.top().ss;
        ll nd = pq.top().ff;
        pq.pop();
        if(nd != dp[now]) continue;
        for(auto &i:E[now]){
            if(dp[i.u] > nd + i.w){
                dp[i.u] = nd + i.w;
                pq.push({dp[i.u], i.u});
            }
        }
    }
    ans = min(ans, dp[V]);
    cout << ans << '\n';
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:2:21: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    2 | #define loop(i,a,b) for(int i = (a); i < (b); i ++)
      |                     ^~~
commuter_pass.cpp:59:5: note: in expansion of macro 'loop'
   59 |     loop(i,1,n+1) dp[i] = INF; dp[S] = 0;
      |     ^~~~
commuter_pass.cpp:59:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   59 |     loop(i,1,n+1) dp[i] = INF; dp[S] = 0;
      |                                ^~
commuter_pass.cpp:2:21: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    2 | #define loop(i,a,b) for(int i = (a); i < (b); i ++)
      |                     ^~~
commuter_pass.cpp:99:5: note: in expansion of macro 'loop'
   99 |     loop(i,1,n+1) dp[i] = INF; dp[U] = 0;
      |     ^~~~
commuter_pass.cpp:99:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   99 |     loop(i,1,n+1) dp[i] = INF; dp[U] = 0;
      |                                ^~

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