제출 #947218

#제출 시각아이디문제언어결과실행 시간메모리
947218steveonalexCommuter Pass (JOI18_commuter_pass)C++11
100 / 100
269 ms28552 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define MASK(i) (1LL << (i)) #define GETBIT(mask, i) (((mask) >> (i)) & 1) #define ALL(v) (v).begin(), (v).end() ll max(ll a, ll b){return (a > b) ? a : b;} ll min(ll a, ll b){return (a < b) ? a : b;} ll LASTBIT(ll mask){return (mask) & (-mask);} int pop_cnt(ll mask){return __builtin_popcountll(mask);} int ctz(ll mask){return __builtin_ctzll(mask);} int logOf(ll mask){return __lg(mask);} mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); ll rngesus(ll l, ll r){return l + (ull) rng() % (r - l + 1);} template <class T1, class T2> bool maximize(T1 &a, T2 b){ if (a < b) {a = b; return true;} return false; } template <class T1, class T2> bool minimize(T1 &a, T2 b){ if (a > b) {a = b; return true;} return false; } template <class T> void printArr(T& container, char separator = ' ', char finish = '\n'){ for(auto item: container) cout << item << separator; cout << finish; } template <class T> void remove_dup(vector<T> &a){ sort(ALL(a)); a.resize(unique(ALL(a)) - a.begin()); } struct P{ long i; ll w; P(){} P(long _i, ll _w){ i = _i, w = _w; } }; struct compare{ bool operator () (P a, P b){return a.w > b.w;} }; const long N = 1e5 + 69; const ll INF = 1e18 + 69; long n, m; long s, t, u, v; vector<P> graph[N]; vector<ll> disS, disT, disU, disV; void dijkstra(long u, vector<ll> &dis){ dis.resize(n+1); for(long i = 1; i<=n; ++i) dis[i] = INF; dis[u] = 0; priority_queue<P, vector<P>, compare> pq; pq.push(P(u, 0)); while(pq.size()){ P u = pq.top(); pq.pop(); for(P v: graph[u.i]) if (minimize(dis[v.i], dis[u.i] + v.w)) pq.push(P(v.i, dis[v.i])); } } ll skill_cap; bool visited[N]; pair<ll, ll> dp[N]; void dfs(long u){ if (visited[u]) return; visited[u] = true; dp[u] = {disU[u], disV[u]}; for(P v: graph[u]) if (disS[v.i] == disS[u] + v.w && disS[v.i] + disT[v.i] == skill_cap){ dfs(v.i); pair<ll, ll> cur = dp[v.i]; minimize(cur.first, disU[u]); minimize(cur.second, disV[u]); if (cur.first + cur.second < dp[u].first + dp[u].second) dp[u] = cur; } } int main(void){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; cin >> s >> t >> u >> v; for(long i = 1; i<=m; ++i){ long u, v, w; cin >> u >> v >> w; graph[u].push_back(P(v, w)); graph[v].push_back(P(u, w)); } dijkstra(s, disS); dijkstra(t, disT); dijkstra(u, disU); dijkstra(v, disV); skill_cap = disS[t]; ll ans = disU[v]; dfs(s); minimize(ans, dp[s].first + dp[s].second); cout << ans << "\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...