제출 #766317

#제출 시각아이디문제언어결과실행 시간메모리
766317OrazBCommuter Pass (JOI18_commuter_pass)C++17
100 / 100
297 ms28996 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <functional> using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; //Dijkstra->set //set.find_by_order(x) x-position value //set.order_of_key(x) number of strictly less elements don't need *set.?? #define N 100005 #define wr cout << "Continue debugging\n"; #define all(x) (x).begin(), (x).end() #define ll long long int #define pii pair <ll, ll> #define pb push_back #define ff first #define ss second ll n, m, s, t, u, v; vector<pii> E[N]; void dijk(int x, vector<ll>&dis){ set<pii> s = {{0, x}}; dis[x] = 0; while(!s.empty()){ int x = (*s.begin()).ss; s.erase(s.begin()); for (auto i : E[x]){ if (dis[i.ff] > dis[x]+i.ss){ s.erase({dis[i.ff], i.ff}); dis[i.ff] = dis[x]+i.ss; s.insert({dis[i.ff], i.ff}); } } } } int main () { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s >> t >> u >> v; while(m--){ int x, y, w; cin >> x >> y >> w; E[x].pb({y, w}); E[y].pb({x, w}); } vector<ll> disu(n+1, 1e17), disv(n+1, 1e17), dis(n+1, 1e17), canu(n+1, 1e17), canv(n+1, 1e17); dijk(v, disv); dijk(u, disu); vector<bool> vis(n+1, 0); priority_queue<pair<pii,ll>, vector<pair<pii,ll>>, greater<pair<pii,ll>>> q; q.push({{0, s}, 0}); dis[s] = 0; while(!q.empty()){ ll w = q.top().ff.ff; int x = q.top().ff.ss, pr = q.top().ss; q.pop(); if (w != dis[x]) continue; if (min(disv[x], canv[pr])+min(disu[x], canu[pr]) < canu[x]+canv[x]){ canv[x] = min(disv[x], canv[pr]); canu[x] = min(disu[x], canu[pr]); } if (vis[x]) continue; vis[x] = 1; for (auto i : E[x]){ if (dis[i.ff] >= dis[x]+i.ss){ dis[i.ff] = dis[x]+i.ss; q.push({{dis[i.ff], i.ff}, x}); } } } cout << min(canu[t]+canv[t], disv[u]); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...