Submission #1265338

#TimeUsernameProblemLanguageResultExecution timeMemory
1265338marcus06Commuter Pass (JOI18_commuter_pass)C++20
31 / 100
321 ms19660 KiB
#include <bits/stdc++.h> using namespace std; using lli = long long; #ifdef LOCAL #include </home/marcus06/CP/Library/debug.h> #else #define debug(...) #endif const int N = int(1e5) + 5; const lli INF = lli(1e18) + 7; int n, m; int S, T, U, V; vector <pair <int, int>> graph[N]; lli from_S[N], from_T[N], from_U[N], from_V[N]; lli f[N], g[N]; void Dijkstra(int src, lli dist[]) { for (int i = 0; i < n; ++i) dist[i] = -1; priority_queue <pair <lli, int>> Q; dist[src] = 0; Q.emplace(0, src); while (!Q.empty()) { auto [d, u] = Q.top(); Q.pop(); d = -d; if (d != dist[u]) continue; for (auto [v, w]: graph[u]) { if (dist[v] == -1 || dist[v] > dist[u] + w) { dist[v] = dist[u] + w; Q.emplace(-dist[v], v); } } } } bool onShortest(int u, int v, int w) { return (from_S[u] + from_T[v] + w == from_S[T]); } bool visited[N]; void dfs(int u) { f[u] = from_U[u]; g[u] = from_V[u]; visited[u] = true; for (auto [v, w]: graph[u]) { if (visited[v] || !onShortest(u, v, w)) continue; dfs(v); f[u] = min(f[u], f[v]); g[u] = min(g[u], g[v]); } } void solve() { cin >> n >> m; cin >> S >> T >> U >> V; --S, --T, --U, --V; for (int i = 0; i < m; ++i) { int u, v, w; cin >> u >> v >> w; --u, --v; graph[u].emplace_back(v, w); graph[v].emplace_back(u, w); } Dijkstra(S, from_S); Dijkstra(T, from_T); Dijkstra(U, from_U); Dijkstra(V, from_V); for (int i = 0; i < n; ++i) { f[i] = g[i] = INF; } dfs(S); lli ans = from_U[V]; for (int i = 0; i < n; ++i) { ans = min(ans, from_U[i] + g[i]); ans = min(ans, from_V[i] + f[i]); } cout << ans << '\n'; } int main() { std::cin.tie(0)->sync_with_stdio(0); #ifdef LOCAL auto begin = std::chrono::high_resolution_clock::now(); #endif int tt = 1; while (tt--) { solve(); } #ifdef LOCAL auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); std::cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; #endif 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...