제출 #1089647

#제출 시각아이디문제언어결과실행 시간메모리
1089647ivan_alexeevCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
1470 ms146744 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; #ifdef lisie_bimbi #else #define endl '\n' #endif typedef long long ll; const ll inf = 1'000'000'000'000'000'000; using namespace std; #pragma GCC optimize("O3") #pragma GCC target("avx,avx2,bmi2,fma,popcnt") //#define int long long struct reb{ int a; int b; ll c; }; vector<ll> dij(vector<vector<pair<int, ll>>> v, int start){ int n = v.size(); vector<ll> d(n, inf); d[start] = 0; set<pair<ll, int>> s; for(int i = 0; i < n; i++){ s.insert({d[i], i}); } while(!s.empty()){ auto [dist, u] = *s.begin(); s.erase(s.begin()); for(auto [i, j] : v[u]){ if(dist + j < d[i]){ s.erase({d[i], i}); d[i] = dist + j; s.insert({d[i], i}); } } } return d; } void solve(){ int n, m; cin >> n >> m; int s, t; cin >> s >> t; int s1, t1; cin >> s1 >> t1; s--;t--;s1--;t1--; vector<reb> r; vector<vector<pair<int, ll>>> v(n); for(int i = 0; i < m; i++){ int a, b, c; cin >> a >> b >> c; a--;b--; r.push_back({a, b, c}); v[a].emplace_back(b, c); v[b].emplace_back(a, c); } auto ds = dij(v, s); auto dt = dij(v, t); vector<vector<pair<int, ll>>> v1(3 * n), v2(3 * n); for(auto [a, b, c] : r){ if(ds[a] + c + dt[b] == ds[t]){ v1[n + a].emplace_back(n + b, 0); v2[n + b].emplace_back(n + a, 0); } if(ds[b] + c + dt[a] == ds[t]){ v1[n + b].emplace_back(n + a, 0); v2[n + a].emplace_back(n + b, 0); } v1[a].emplace_back(b, c); v1[b].emplace_back(a, c); v1[2 * n + a].emplace_back(2 * n + b, c); v1[2 * n + b].emplace_back(2 * n + a, c); v2[a].emplace_back(b, c); v2[b].emplace_back(a, c); v2[2 * n + a].emplace_back(2 * n + b, c); v2[2 * n + b].emplace_back(2 * n + a, c); } for(int i = 0; i < n; i++){ v1[i].emplace_back(i + n, 0); v1[i + n].emplace_back(i + 2 * n, 0); v2[i].emplace_back(i + n, 0); v2[i + n].emplace_back(i + 2 * n, 0); } auto d = dij(v1, s1); auto d1 = dij(v2, s1); cout << min(d[t1 + 2 * n], d1[t1 + 2 * n]) << endl; } signed main(){ #ifdef lisie_bimbi freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #else cin.tie(nullptr)->sync_with_stdio(false); #endif cout << setprecision(5) << fixed; int _ = 1; //cin >> t; while(_--){ solve(); } return 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...