Submission #679433

#TimeUsernameProblemLanguageResultExecution timeMemory
679433Chal1shkanEvacuation plan (IZhO18_plan)C++14
35 / 100
1086 ms36768 KiB
#include <bits/stdc++.h> # define pb push_back # define ff first # define ss second # define nl "\n" typedef long long ll; typedef unsigned long long ull; typedef long double ld; const ll maxn = 1e5 + 25; const ll maxl = 22 + 0; const ll inf = 1e18 + 0; const ll mod = 998244353; const ll dx[] = {-1, 1, 0, 0}; const ll dy[] = {0, 0, -1, 1}; using namespace std; ll n, m, k, q, d[maxn]; vector <pair <ll, ll> > g[maxn]; ll ans[maxn]; void dijkstra (ll s) { d[s] = 0; set <pair <ll, ll> > q; q.insert({0, s}); while (!q.empty()) { ll v = q.begin() -> ss; q.erase(q.begin()); for (auto i : g[v]) { ll to = i.ff, w = i.ss; if (d[v] + w < d[to]) { q.erase({d[to], to}); d[to] = d[v] + w; q.insert({d[to], to}); } } } } void bfs (ll s) { fill(ans, ans + 1 + n, 0); ans[s] = d[s]; set <pair <ll, ll> > q; q.insert({-ans[s], s}); while (!q.empty()) { ll v = q.begin() -> ss; q.erase(q.begin()); for (auto i : g[v]) { ll to = i.ff, w = i.ss; if (min(ans[v], d[to]) > ans[to]) { q.erase({-ans[to], to}); ans[to] = min(ans[v], d[to]); q.insert({-ans[to], to}); } } } } void ma1n () { cin >> n >> m; for (ll i = 1; i <= n; ++i) d[i] = inf; for (ll i = 1; i <= m; ++i) { ll u, v, w; cin >> u >> v >> w; g[u].pb({v, w}); g[v].pb({u, w}); } cin >> k; for (ll i = 1; i <= k; ++i) { ll v; cin >> v; dijkstra(v); } if (n <= 15) { cin >> q; for (ll i = 1; i <= q; ++i) { ll u, v; cin >> u >> v; bfs(u); cout << ans[v] << nl; } } else { cin >> q; for (ll i = 1; i <= q; ++i) { ll u, v; cin >> u >> v; cout << min(d[u], d[v]) << nl; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("mooyomooyo.in", "r", stdin); // freopen("mooyomooyo.out", "w", stdout); int ttt = 1; // cin >> ttt; for (int test = 1; test <= ttt; ++test) { // cout << "Case " << test << ":" << nl; ma1n(); } return 0; }

Compilation message (stderr)

plan.cpp: In function 'void bfs(ll)':
plan.cpp:59:27: warning: unused variable 'w' [-Wunused-variable]
   59 |             ll to = i.ff, w = i.ss;
      |                           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...