제출 #728547

#제출 시각아이디문제언어결과실행 시간메모리
728547beabossCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
465 ms29048 KiB
#include "bits/stdc++.h" using namespace std; #define s second #define f first #define pb push_back typedef long long ll; typedef pair<ll, ll> pii; const ll INF = 1e17 + 10ll; int main() { ll n, m; cin >> n >> m; ll s, t; cin >> s >> t; ll u, v; cin >> u >> v; u--;v--;s--;t--; vector<vector<pii> > adj(n); for (ll i = 0; i < m; i++) { ll a,b,w; cin >> a >> b >> w; adj[--a].push_back({--b, w}); adj[b].push_back({a, w}); } vector<ll> distu(n, -1); vector<ll> distv(n, -1); // distu[u]=0; // distv[v]=0; priority_queue<pii> q; q.push({0, u}); while (!q.empty()) { ll cur = q.top().s; ll dist = q.top().f; q.pop(); if (distu[cur] >= 0ll) continue; distu[cur] = -dist; // cout << cur << endl; for (auto val: adj[cur]) { if (distu[val.f] == -1ll) { q.push({-distu[cur] - val.s, val.f}); } } } q.push({0, v}); while (!q.empty()) { ll cur = q.top().s; ll dist = q.top().f; q.pop(); if (distv[cur] >= 0ll) continue; distv[cur] = -dist; // cout << cur << endl; for (auto val: adj[cur]) { if (distv[val.f] == -1ll) { q.push({-distv[cur] - val.s, val.f}); } } } vector<ll> minans(n, INF); vector<ll> minprev(n, INF); vector<ll> minans1(n, INF); vector<ll> minprev1(n, INF); vector<ll> dist(n, -1); priority_queue<pair<ll, pii> > bq; for (auto val: adj[s]) bq.push({-val.s, {val.f, s}}); dist[s]=0; minprev[s] = distu[s]; minans[s] = distu[v]; minprev1[s] = distv[s]; minans1[s] = distv[u]; assert(distu[v]==distv[u]); while (!bq.empty()) { ll cur = bq.top().s.f; ll prev = bq.top().s.s; ll d = bq.top().f; bq.pop(); if (-d > dist[cur] && dist[cur]!=-1) continue; bool prevdone = (dist[cur] != -1); assert(dist[cur] == -1 || dist[cur]==-d); dist[cur] = -d; minprev[cur] = min(min(minprev[prev], distu[cur]), minprev[cur]); minans[cur] = min(min(minans[prev], minprev[cur] + distv[cur]), minans[cur]); minprev1[cur] = min(min(minprev1[prev], distv[cur]), minprev1[cur]); minans1[cur] = min(min(minans1[prev], minprev1[cur] + distu[cur]), minans1[cur]); // cout << cur << minprev[cur] << endl; if (prevdone) continue; for (auto val: adj[cur]) { if (dist[val.f] == -1) { bq.push({-dist[cur] - val.s, {val.f, cur}}); } } } cout << min(minans[t], minans1[t]) << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...