Submission #880378

#	Time	Username	Problem	Language	Result	Execution time	Memory
880378		niter	Commuter Pass (JOI18_commuter_pass)	C++14	16 / 100	273 ms	45564 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], DP[mxn][2];
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();
    }
//    loop(i,1,n+1){
//        opa(i) opa(vis[i]) op(n_vis[i])
//    }
    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});
            F[near].pb({far, i.w});
            F[far].pb({near, i.w});
            G[far].pb({near, 0});
            G[far].pb({near, i.w});
            G[near].pb({far, i.w});
        }
        else{
            F[i.ff].pb({i.ss, i.w});
            F[i.ss].pb({i.ff, i.w});
            G[i.ff].pb({i.ss, i.w});
            G[i.ss].pb({i.ff, i.w});
        }
    }
    loop(i,1,n+1) DP[i][0] = DP[i][1] = INF;
    DP[U][true] = DP[U][false] = 0;
    priority_queue<pair<ll,pair<int,bool>>, vector<pair<ll,pair<int,bool>>>, greater<pair<ll,pair<int,bool>>>> PQ;
    PQ.push({0, {U, true}});
    PQ.push({0, {U, false}});
    while(!PQ.empty()){
        int now = PQ.top().ss.ff;
        bool can = PQ.top().ss.ss;
        ll dis = PQ.top().ff;
        PQ.pop();
        if(dis != DP[now][can]) continue;
        for(auto &i:F[now]){
            if((!can) && i.w == 0) continue;
            bool nxt_can = can && (i.w == 0);
            if(dis + i.w < DP[i.u][nxt_can]){
                DP[i.u][nxt_can] = dis + i.w;
                PQ.push({DP[i.u][nxt_can], {i.u, nxt_can}});
            }
        }
    }
    ll ans = min(DP[V][0], DP[V][1]);


    loop(i,1,n+1) DP[i][0] = DP[i][1] = INF;
    DP[U][true] = DP[U][false] = 0;
    PQ.push({0, {U, true}});
    PQ.push({0, {U, false}});
    while(!PQ.empty()){
        int now = PQ.top().ss.ff;
        bool can = PQ.top().ss.ss;
        ll dis = PQ.top().ff;
        PQ.pop();
        if(dis != DP[now][can]) continue;
        for(auto &i:G[now]){
            if((!can) && i.w == 0) continue;
            bool nxt_can = can && (i.w == 0);
            if(dis + i.w < DP[i.u][nxt_can]){
                DP[i.u][nxt_can] = dis + i.w;
                PQ.push({DP[i.u][nxt_can], {i.u, nxt_can}});
            }
        }
    }
    ans = min(ans, min(DP[V][0], DP[V][1]));
    cout << ans;
}

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;
      |                                ^~

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