제출 #1091148

#제출 시각아이디문제언어결과실행 시간메모리
1091148orcslopCommuter Pass (JOI18_commuter_pass)C++17
0 / 100
196 ms47280 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define all(x) begin(x), end(x) #define sz(x) (int) (x).size() #define f first #define s second #define mkp make_pair #define pii pair<int, int> bool ckmin(int& a, int b){ return b < a ? a = b, true : false; } bool ckmax(int& a, int b){ return b > a ? a = b, true : false; } const int N = 1e5 + 5; int n, m; int v[4]; int d[4][N]; int dp[3][N]; bool vis[N]; vector<pii> adj[N]; vector<int> nadj[N], ts, rts; priority_queue<pii, vector<pii>, greater<pii>> pq; void dfs(int node){ for(auto x : nadj[node]){ if(!vis[x]){ vis[x] = 1; dfs(x); } } ts.pb(node); } int32_t main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i = 0; i < 4; i++){ cin >> v[i]; v[i]--; } for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; a--; b--; adj[a].pb({c, b}); adj[b].pb({c, a}); } for(int i = 0; i < 4; i++){ fill(d[i], d[i] + n, 1e18); d[i][v[i]] = 0; pq.push({0, v[i]}); while(!pq.empty()){ pii curr = pq.top(); pq.pop(); if(d[i][curr.s] != curr.f) continue; for(auto x : adj[curr.s]){ if(d[i][x.s] > curr.f + x.f){ d[i][x.s] = curr.f + x.f; pq.push({d[i][x.s], x.s}); } } } } int best = d[0][v[1]]; for(int i = 0; i < n; i++){ for(auto x : adj[i]){ if(d[0][i] + d[1][x.s] + x.f == best){ nadj[i].pb(x.s); } } } //topsort dfs(v[0]); reverse(all(ts)); rts.resize(sz(ts)); for(int i = 0; i < sz(ts); i++){ rts[ts[i]] = i; } // calculate dp[2][N]; // ans will be dp[0][0] + dp[1][0]; for(int i = sz(ts) - 1; i >= 0; i--){ dp[0][i] = d[2][ts[i]]; dp[1][i] = d[3][ts[i]]; dp[2][i] = dp[0][i] + dp[1][i]; for(auto x : nadj[ts[i]]){ ckmin(dp[2][i], dp[2][rts[x]]); ckmin(dp[2][i], dp[0][i] + dp[1][rts[x]]); ckmin(dp[2][i], dp[1][i] + dp[0][rts[x]]); } for(auto x : nadj[ts[i]]){ ckmin(dp[0][i], dp[0][rts[x]]); ckmin(dp[1][i], dp[1][rts[x]]); } } cout << min(d[2][v[3]], dp[2][0]) << '\n'; return 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...