제출 #93064

#제출 시각아이디문제언어결과실행 시간메모리
93064MoysenkoEvacuation plan (IZhO18_plan)C++17
54 / 100
4006 ms76684 KiB
/*ЗАПУСКАЕМ ░ГУСЯ░▄▀▀▀▄░РАБОТЯГИ░░ ▄███▀░◐░░░▌░░░░░░░ ░░░░▌░░░░░▐░░░░░░░ ░░░░▐░░░░░▐░░░░░░░ ░░░░▌░░░░░▐▄▄░░░░░ ░░░░▌░░░░▄▀▒▒▀▀▀▀▄ ░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄ ░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄ ░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░░░▌▌░▌▌░░░░░ ░░░░░░░░░▄▄▌▌▄▌▌░░░░░ НАСТРОЙКА НА КРИТЫ ██████████████] 100% СОЧНОСТИ*/ #include <iostream> #include <vector> #include <algorithm> #include <set> #include <map> #include <string> #include <math.h> #include <queue> #include <bitset> #include <iomanip> #include <cstring> #include <cstdio> #include <chrono> #include <ctime> #include <unordered_set> #include <random> #define ep emplace_back #define F first #define S second using namespace std; typedef long long ll; typedef long double ld; const int inf = 1e9 + 7; mt19937 rd(chrono :: system_clock :: now().time_since_epoch().count()); #pragma GCC optimize("unroll-loops") // развернуть цикл #pragma GCC optimize("Ofast") // скомпилировать с о3 /* #pragma GCC optimize("no-stack-protector") // что-то со стеком #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") // оптимизации процессора #pragma GCC optimize("fast-math") // оптимизации сопроцессора */ const int siz = 1e5 + 10; vector<pair<int, int> > g[siz]; int dist[siz], n; vector<int> aes; set<int> edg[siz]; bool used[siz]; void Get_dist(){ for (int i = 0; i < n; i++) dist[i] = inf; set<pair<int, int> > st; for (auto &j : aes) st.insert({0, j}), dist[j] = 0; int v, d; while (!st.empty()){ d = st.begin()->F; v = st.begin()->S; st.erase(st.begin()); if (dist[v] < d) continue; for (auto &u : g[v]) if (dist[u.F] > dist[v] + u.S) dist[u.F] = dist[v] + u.S, st.insert({dist[u.F], u.F}); } } int mni[siz]; int Solve(int s, int f){ set<pair<int, int> > st; fill(mni, mni + n, 0); mni[s] = dist[s]; st.insert({dist[s], s}); int v, d; while (!st.empty()){ auto it = --st.end(); v = it->S; d = it->F; st.erase(it); if (mni[v] > d) continue; if (v == f) break; for (auto &u : edg[v]) if (mni[u] < min(dist[u], d)) mni[u] = min(dist[u], d), st.insert({mni[u], u}); } return mni[f]; } int main(){ ios::sync_with_stdio(0), cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int m; cin >> n >> m; int i, v, u, w; for (i = 0; i < m; i++){ cin >> v >> u >> w; v--, u--; g[v].ep(u, w); g[u].ep(v, w); edg[v].insert(u); edg[u].insert(v); } int k; cin >> k; aes.resize(k); for (auto &j : aes){ cin >> j; j--; } Get_dist(); int q; cin >> q; while (q--){ cin >> v >> u; v--, u--; //cout << dist[v] << ' ' << dist[u] << '\n'; if (edg[v].count(u)) cout << min(dist[v], dist[u]) << '\n'; else cout << Solve(v, u) << '\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...
#Verdict Execution timeMemoryGrader output
Fetching results...