Submission #680451

#TimeUsernameProblemLanguageResultExecution timeMemory
680451NeosCommuter Pass (JOI18_commuter_pass)C++14
16 / 100
338 ms26212 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define sz(x) (int)x.size() #define getBit(x, i) ((x) >> (i) & 1) #define rep(i, begin, end) for (ll i = (begin); i <= (end); i++) #define rrep(i, begin, end) for (ll i = (begin); i >= (end); i--) typedef long long ll; typedef pair<ll, ll> ii; template <class T> bool minimize(T &a, const T &b) { if(a > b) {a = b; return 1;} return 0; } template <class T> bool maximize(T &a, const T &b) { if(a < b) {a = b; return 1;} return 0; } const int N = 1e5 + 7; int n, m, s, t, x, y; bool done[N]; ll d[N][4], f[N], ans = 1e18; vector<ii> adj[N]; vector<int> dag[N]; void dijk(int s, int i) { priority_queue<ii, vector<ii>, greater<ii>> pq; pq.push(ii(0, s)); d[s][i] = 0; while (sz(pq)) { ii u = pq.top(); pq.pop(); if (u.fi != d[u.se][i]) continue; for (auto [v, w]: adj[u.se]) { if (minimize(d[v][i], d[u.se][i] + w)) { pq.push(ii(d[v][i], v)); } } } } void dfs1(int u) { done[u] = 1; f[u] = d[u][3]; // shortest path from y->u for (auto [v, w]: adj[u]) if (d[u][0] + d[v][1] + w == d[t][0]) { if (!done[v]) dfs1(v); minimize(f[u], f[v]); } minimize(ans, d[u][2] + f[u]); } void dfs2(int u) { done[u] = 1; f[u] = d[u][3]; // shortest path from y->u for (auto [v, w]: adj[u]) if (d[u][1] + d[v][0] + w == d[t][0]) { if (!done[v]) dfs2(v); minimize(f[u], f[v]); } minimize(ans, d[u][2] + f[u]); } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> s >> t >> x >> y; rep(i, 1, m) { int u, v, w; cin >> u >> v >> w; adj[u].pb(ii(v, w)); adj[v].pb(ii(u, w)); } memset(d, 0x3f, sizeof d); dijk(s, 0); dijk(t, 1); dijk(x, 2); dijk(y, 3); ans = d[y][2]; memset(f, 0x3f, sizeof f); dfs1(s); memset(f, 0x3f, sizeof f); dfs2(t); cout << ans; }

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijk(int, int)':
commuter_pass.cpp:41:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         for (auto [v, w]: adj[u.se]) {
      |                   ^
commuter_pass.cpp: In function 'void dfs1(int)':
commuter_pass.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for (auto [v, w]: adj[u]) if (d[u][0] + d[v][1] + w == d[t][0]) {
      |               ^
commuter_pass.cpp: In function 'void dfs2(int)':
commuter_pass.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for (auto [v, w]: adj[u]) if (d[u][1] + d[v][0] + w == d[t][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...