제출 #880378

#제출 시각아이디문제언어결과실행 시간메모리
880378niterCommuter Pass (JOI18_commuter_pass)C++14
16 / 100
273 ms45564 KiB
#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; }

컴파일 시 표준 에러 (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;
      |                                ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...