제출 #924100

#제출 시각아이디문제언어결과실행 시간메모리
924100TAhmed33Commuter Pass (JOI18_commuter_pass)C++98
100 / 100
270 ms30576 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize ("trapv") typedef long long ll; const ll inf = 1e18; const int MAXN = 1e5 + 25; vector <pair <ll, ll>> adj[MAXN]; int n, m, s, t, u, v; vector <int> adj2[MAXN]; ll dist[MAXN], dist2[MAXN]; ll dp[MAXN][2]; ll ans (int pos, int c) { ll &ret = dp[pos][c]; if (ret != -1) return ret; if (c == 0) { ret = dist[pos] + ans(pos, 1); ll mn = inf; for (auto j : adj2[pos]) mn = min(mn, ans(j, 0)); ret = min(ret, mn); } else { ret = dist2[pos]; ll mn = inf; for (auto j : adj2[pos]) mn = min(mn, ans(j, 1)); ret = min(ret, mn); } return ret; } ll ans2 (int pos, int c) { ll &ret = dp[pos][c]; if (ret != -1) return ret; if (c == 0) { ret = dist2[pos] + ans2(pos, 1); ll mn = inf; for (auto j : adj2[pos]) mn = min(mn, ans2(j, 0)); ret = min(ret, mn); } else { ret = dist[pos]; ll mn = inf; for (auto j : adj2[pos]) mn = min(mn, ans2(j, 1)); ret = min(ret, mn); } return ret; } int main () { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> s >> t >> u >> v; for (int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; adj[a].push_back({b, c}); adj[b].push_back({a, c}); } for (int i = 1; i <= n; i++) dist[i] = inf; dist[s] = 0; priority_queue <pair <ll, ll>, vector <pair <ll, ll>>, greater <>> pq; pq.push({0, s}); while (!pq.empty()) { auto k = pq.top(); pq.pop(); if (k.first > dist[k.second]) continue; for (auto j : adj[k.second]) { if (j.second + k.first < dist[j.first]) { dist[j.first] = k.first + j.second; pq.push({dist[j.first], j.first}); } } } for (int i = 1; i <= n; i++) dist2[i] = inf; dist2[t] = 0; pq.push({0, t}); while (!pq.empty()) { auto k = pq.top(); pq.pop(); if (k.first > dist2[k.second]) continue; for (auto j : adj[k.second]) { if (j.second + k.first < dist2[j.first]) { dist2[j.first] = k.first + j.second; pq.push({dist2[j.first], j.first}); } } } for (int i = 1; i <= n; i++) { for (auto j : adj[i]) { if (dist[i] + j.second == dist[j.first] && dist2[i] == dist2[j.first] + j.second && dist[i] + dist2[j.first] + j.second == dist[t]) { adj2[i].push_back(j.first); } } } for (int i = 1; i <= n; i++) dist[i] = dist2[i] = inf; dist[u] = 0; pq.push({0, u}); while (!pq.empty()) { auto k = pq.top(); pq.pop(); if (k.first > dist[k.second]) continue; for (auto j : adj[k.second]) { if (j.second + k.first < dist[j.first]) { dist[j.first] = k.first + j.second; pq.push({dist[j.first], j.first}); } } } dist2[v] = 0; pq.push({0, v}); while (!pq.empty()) { auto k = pq.top(); pq.pop(); if (k.first > dist2[k.second]) continue; for (auto j : adj[k.second]) { if (j.second + k.first < dist2[j.first]) { dist2[j.first] = k.first + j.second; pq.push({dist2[j.first], j.first}); } } } memset(dp, -1, sizeof(dp)); ll mn = inf; for (int i = 1; i <= n; i++) mn = min(mn, ans(i, 0)); ll mn2 = inf; memset(dp, -1, sizeof(dp)); for (int i = 1; i <= n; i++) mn2 = min(mn2, ans2(i, 0)); cout << min({dist[v], mn2, mn}) << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...