Submission #1167410

#TimeUsernameProblemLanguageResultExecution timeMemory
1167410GoBananas69Commuter Pass (JOI18_commuter_pass)C++20
15 / 100
356 ms35908 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <queue> typedef long long ll; using namespace std; const ll inf = 1e18; vector<ll> du, dv, ds, dt; vector<ll> p, path; vector<bool> vis; void dijkstra(ll s, vector<ll> &dist, vector<vector<pair<ll, ll>>> &adj) { fill(vis.begin(), vis.end(), false); priority_queue<pair<ll, ll>> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { ll u = pq.top().second; // ll w = pq.top().first; pq.pop(); if (vis[u]) continue; vis[u] = true; for (auto &p: adj[u]) { ll v = p.first; ll w = p.second; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; pq.push({-dist[v], v}); } } } } void find(ll s, ll t, vector<vector<pair<ll, ll>>> &adj) { vector<ll> dist(adj.size(), inf); fill(vis.begin(), vis.end(), false); priority_queue<pair<ll, ll>> pq; dist[s] = 0; pq.push({0, s}); while (!pq.empty()) { ll u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (auto &e: adj[u]) { ll v = e.first; ll w = e.second; if (dist[v] > dist[u] + w) { p[v] = u; dist[v] = dist[u] + w; pq.push({-dist[v], v}); } } } for (ll v = t; v != s; v = p[v]) { path.push_back(v); } path.push_back(s); reverse(path.begin(), path.end()); } signed main() { cin.tie() -> sync_with_stdio(0); ll n, m, s, t, a, b; cin >> n >> m >> s >> t >> a >> b; vector<vector<pair<ll, ll>>> adj(n + 1); vector<vector<pair<ll, ll>>> adj1; dv.resize(n + 1, inf); du.resize(n + 1, inf); ds.resize(n + 1, inf); dt.resize(n + 1, inf); p.resize(n + 1, -1); vis.resize(n + 1); for (ll i = 0; i<m; ++i) { ll u, v, w; cin >> u >> v >> w; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } dijkstra(a, du, adj); dijkstra(b, dv, adj); dijkstra(s, ds, adj); dijkstra(t, dt, adj); find(s, t, adj); adj1 = adj; for (ll i = 1; i<path.size(); ++i) { ll u = path[i - 1]; ll v = path[i]; adj1[u].push_back({v, 0}); adj1[v].push_back({u, 0}); } dijkstra(a, du, adj1); dijkstra(b, dv, adj1); ll res = min(du[b], dv[a]); ll res1; if (n <= 300) { vector<vector<ll>> dist(n + 1, vector<ll>(n + 1, inf)); for (ll i = 1; i<=n; ++i) { dijkstra(i, dist[i], adj); } res1 = min(du[b], dv[a]); for(ll i = 1; i<=n; ++i) { for(ll j = 1; j<=n; ++j) { if(ds[i] + dt[j] + dist[i][j] == ds[t]) { res1 = min(res1, du[i] + dv[j]); res1 = min(res1, du[j] + dv[i]); } } } res = min(res, res1); } cout << res << '\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...