Submission #1167406

#TimeUsernameProblemLanguageResultExecution timeMemory
1167406GoBananas69Commuter Pass (JOI18_commuter_pass)C++20
Compilation error
0 ms0 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <queue> typedef long long ll; using namespace std; const ll inf = 1e18; vector<vector<pair<ll, ll>>> adj; vector<ll> du, dv, ds, dt; vector<ll> p, path; vector<bool> vis; void dijkstra(ll s, vector<ll> &dist) { 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<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() { //this solution assumes only one unique minimum path from s to t cin.tie() -> sync_with_stdio(0); ll n, m, s, t, a, b; cin >> n >> m >> s >> t >> a >> b; adj.resize(n + 1); 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); dijkstra(b, dv); dijkstra(s, ds); dijkstra(t, dt); find(s, t); for (ll i = 1; i<path.size(); ++i) { ll u = path[i - 1]; ll v = path[i]; adj[u].push_back({v, 0}); adj[v].push_back({u, 0}); } // cout << '\n'; 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]); } 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'; }

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:100:5: error: 'res' was not declared in this scope
  100 |     res = min(du[b], dv[a]);
      |     ^~~