제출 #1073352

#제출 시각아이디문제언어결과실행 시간메모리
1073352sanoCommuter Pass (JOI18_commuter_pass)C++14
100 / 100
663 ms41320 KiB
#include<iostream> #include<vector> #include<queue> #include<deque> #include<string> #include<fstream> #include<algorithm> #include <iomanip> #include<map> #include <set> #include <unordered_map> #include <stack> #include <unordered_set> #include <cmath> #define ll long long #define For(i, n) for(ll i = 0; i < (ll)n; i++) #define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++) #define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--) #define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--) #define vec vector #define ff first #define ss second #define pb push_back #define shit short ll #define pii pair<ll, ll> #define NEK 1000000000000000000 #define mod 1000000007 #define mod2 1000000009 #define rsz resize #define prv1 43 #define prv2 47 #define D 8 using namespace std; struct sr { ll w; pii s; bool operator<(const sr& other) const { return w < other.w; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll n, m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; vec<vec<pii>> g(n); For(i, m) { ll a, b, c; cin >> a >> b >> c; a--; b--; g[a].push_back({ b, c }); g[b].push_back({ a, c }); } vec<ll> ds(n, -1), dt(n, -1); priority_queue<pii> q; q.push({ 0, s }); while (!q.empty()) { ll som = q.top().ss; ll w = q.top().ff * (-1); q.pop(); if (ds[som] != -1) continue; ds[som] = w; for (auto i : g[som]) { if (ds[i.ff] != -1) continue; q.push({ (-1) * (w + i.ss), i.ff }); } } q.push({ 0, t }); while (!q.empty()) { ll som = q.top().ss; ll w = q.top().ff * (-1); q.pop(); if (dt[som] != -1) continue; dt[som] = w; for (auto i : g[som]) { if (dt[i.ff] != -1) continue; q.push({ (-1) * (w + i.ss), i.ff }); } } ll mini = NEK; vec<ll> hod(n); For(i, n) { hod[i] = ds[i] + dt[i]; mini = min(mini, ds[i] + dt[i]); } priority_queue<sr> q2; vec<vec<ll>> d(n, vec<ll>(3, -1)); q2.push({ 0, { u, 1 } }); while (!q2.empty()) { pii som = q2.top().s; ll w = q2.top().w * (-1); q2.pop(); if (d[som.ff][som.ss] != -1) continue; d[som.ff][som.ss] = w; if ((som.ff == u || som.ff == v) && som.ss == 2) { q2.push({ (-1) * w, {som.ff, 0} }); continue; } if (som.ss == 0) { for (auto i : g[som.ff]) { if (d[i.ff][0] != -1) continue; q2.push({ (-1) * (w + i.ss), { i.ff, 0 } }); } } if(som.ss == 1) { for (auto i : g[som.ff]) { if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff])) { if (d[i.ff][2] == -1) { q2.push({ (-1) * w, {i.ff, 2} }); } } if (d[i.ff][1] != -1) continue; q2.push({ (-1) * (w + i.ss), {i.ff, 1} }); } } if (som.ss == 2) { for (auto i : g[som.ff]) { if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff]) && d[i.ff][2] == -1) { q2.push({ (-1) * w, {i.ff, 2} }); } if (d[i.ff][0] != -1) continue; q2.push({ (-1) * (w + i.ss), {i.ff, 0} }); } } } For(i, 3) if (d[v][i] == -1) d[v][i] = NEK; ll nasemin = NEK; For(i, 3) nasemin = min(nasemin, d[v][i]); d.clear(); d.resize(n, vec<ll>(3, -1)); q2.push({ 0, {v, 1} }); while (!q2.empty()) { pii som = q2.top().s; ll w = q2.top().w * (-1); q2.pop(); if (d[som.ff][som.ss] != -1) continue; d[som.ff][som.ss] = w; if ((som.ff == u || som.ff == v) && som.ss == 2) { q2.push({ (-1) * w, {som.ff, 0} }); continue; } if (som.ss == 0) { for (auto i : g[som.ff]) { if (d[i.ff][0] != -1) continue; q2.push({ (-1) * (w + i.ss), { i.ff, 0 } }); } } if (som.ss == 1) { for (auto i : g[som.ff]) { if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff])) { if (d[i.ff][2] == -1) { q2.push({ (-1) * w, {i.ff, 2} }); } } if (d[i.ff][1] != -1) continue; q2.push({ (-1) * (w + i.ss), {i.ff, 1} }); } } if (som.ss == 2) { for (auto i : g[som.ff]) { if (hod[i.ff] == mini && hod[som.ff] == mini && ((ds[som.ff] + i.ss) == ds[i.ff]) && d[i.ff][2] == -1) { q2.push({ (-1) * w, {i.ff, 2} }); } if (d[i.ff][0] != -1) continue; q2.push({ (-1) * (w + i.ss), {i.ff, 0} }); } } } For(i, 3) if (d[u][i] == -1) d[u][i] = NEK; For(i, 3) nasemin = min(nasemin, d[u][i]); cout << nasemin << endl; 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...