Submission #591036

#TimeUsernameProblemLanguageResultExecution timeMemory
591036piOOECommuter Pass (JOI18_commuter_pass)C++17
100 / 100
872 ms33524 KiB
//#define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; //randoms mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); #define ll long long #define trace(x) cout << #x << " = " << (x) << endl; #define all(x) x.begin(), (x).end() #define rall(x) x.rbegin(), (x).rend() #define unique(x) x.erase(unique(all(x)), (x).end()) #define ld long double #define sz(s) (int) size(s) const int N = 100001; const ll infL = 1e18; const int infI = 1e9 + 7; const ll mod = 998244353; ll dist[4][N]; //s, t, u, v vector<pair<int, ll>> g[N]; vector<int> gr[N], tops; bool VisT[N], used[N]; ll minU[N], minV[N]; void dfs(int v) { used[v] = true; for (int to : gr[v]) { if (!used[to]) dfs(to); } tops.push_back(v); } int s, t, u, v, n; void calcDist(int i) { for (int j = 0; j < n; ++j) dist[i][j] = infL; if (i == 0) dist[i][s] = 0; else if (i == 1) dist[i][t] = 0; else if (i == 2) dist[i][u] = 0; else dist[i][v] = 0; set<pair<ll, int>> st; for (int j = 0; j < n; ++j) st.insert({dist[i][j], j}); while (!st.empty()) { auto[w, V] = *st.begin(); st.erase(st.begin()); for (auto[to, W] : g[V]) { ll val = W + w; if (val < dist[i][to]) { st.erase({dist[i][to], to}); dist[i][to] = val; st.insert({dist[i][to], to}); } } } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int m; cin >> n >> m >> s >> t >> u >> v; --s, --t, --u, --v; for (int i = 0; i < m; ++i) { int a, b, w; cin >> a >> b >> w; --a, --b; g[a].emplace_back(b, w); g[b].emplace_back(a, w); } for (int i = 0; i < 4; ++i) calcDist(i); for (int i = 0; i < n; ++i) { for (auto[to, W] : g[i]) { if (dist[0][i] + W == dist[0][to]) { gr[i].push_back(to); } } } for (int i = 0; i < n; ++i) minU[i] = minV[i] = infL; for (int i = 0; i < n; ++i) { if (!used[i]) dfs(i); } ll ans = dist[2][v]; for (int x : tops) { if (x == t) VisT[x] = true; for (int to : gr[x]) { if (VisT[to]) { VisT[x] = true; minU[x] = min(minU[x], minU[to]); minV[x] = min(minV[x], minV[to]); } } if (VisT[x]) { ans = min({ans, minU[x] + dist[3][x], minV[x] + dist[2][x]}); minU[x] = min(minU[x], dist[2][x]); minV[x] = min(minV[x], dist[3][x]); } } cout << ans; 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...