// Src : Vux2Code
/* Note :
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pusb push_back
#define popb pop_back
#define pusf push_front
#define popf pop_front
#define vec3d vector<vector<vector<ll>>>
#define vec2d vector<vector<ll>>
#define vec1d vector<ll>
vec3d set3 (ll x, ll y, ll z, ll val = 0) {return vec3d (x, vec2d (y, vec1d (z, val)));}
vec2d set2 (ll x, ll y, ll val = 0) {return vec2d (x, vec1d (y, val));}
// debug (+20)
#define debug(...) debug_impl(#__VA_ARGS__, __VA_ARGS__)
template<typename... Args>
void debug_impl(const char* names, Args&&... args) {
vector<string> _names;
{
istringstream ss(names);
string token;
while (getline(ss, token, ',')) {
auto l = token.find_first_not_of(" ");
auto r = token.find_last_not_of(" ");
if (l == string::npos) _names.push_back("");
else _names.push_back(token.substr(l, r - l + 1));
}
}
cerr << "(";
size_t _i = 0;
int _dummy[] = { 0, ((cerr << _names[_i] << " : " << args << (++_i < _names.size() ? ", " : "")), 0)... };
(void)_dummy;
cerr << ")" << endl;
}
// handy for loops
#define forinc(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fordec(i, a, b) for (ll i = (a); i >= (b); --i)
#define foreach(i, j) for (ll i : (j))
#define all(a) (a).begin (), (a). end ()
#define uni(a) (a).erase(unique((a).begin(), (a). end ()), (a). end ())
const ll maxN = 1e6 + 5, maxLog = 20, inf64 = 1e18, inf32 = 1e9, mod = 1e9 + 7;
void maxi(ll &x, ll y) { x = max(x, y); }
void mini(ll &x, ll y) { x = min(x, y); }
/* ---------HASHING-------- */
// const base = 31, mod2 = 1e9 + 9;
/* ---------BITMASK-------- */
// ll count(ll x) { return __builtin_popcountll(x); }
// ll fst(ll x) { return 63 - __builtin_clzll(x); }
// ll last(ll x) { return __builtin_ctzll(x); }
// bool bit(ll x, ll y) { return ((x >> y) & 1); }
ll t = 1;
ll n, m, ds [maxN], du [maxN], dv [maxN], du2 [maxN], dv2 [maxN];
pll r1, r2;
priority_queue <pll, vector <pll>, greater <pll>> pq;
queue <ll> q;
vector <pll> adj [maxN];
vec1d topo, pr [maxN], ch [maxN];
bool ckTopo [maxN];
void dijk (ll root, ll d []) {
fill (d, d + n + 1, inf64);
d [root] = 0;
pq. push ({d [root], root});
while (!pq. empty ()) {
ll dis = pq. top (). fi;
ll id = pq. top (). se;
pq. pop ();
if (dis != d [id]) continue;
for (pll i : adj [id]) {
if (d [i. fi] > d [id] + i. se) {
d [i. fi] = d [id] + i. se;
pq. push ({d [i. fi], i. fi});
}
}
}
}
void solve() {
cin >> n >> m;
cin >> r1. fi >> r1. se;
cin >> r2. fi >> r2. se;
forinc (i, 1, m) {
int u, v, w;
cin >> u >> v >> w;
adj [u]. pusb ({v, w});
adj [v]. pusb ({u, w});
}
memset (ds, 0x3f, sizeof ds);
ds [r1. fi] = 0;
pq. push ({ds [r1. fi], r1. fi});
while (!pq. empty ()) {
ll dis = pq. top (). fi;
ll id = pq. top (). se;
pq. pop ();
if (dis != ds [id]) continue;
for (pll i : adj [id]) {
if (ds [i. fi] > ds [id] + i. se) {
ds [i. fi] = ds [id] + i. se;
pq. push ({ds [i. fi], i. fi});
pr [i. fi]. clear ();
}
if (ds [i. fi] == ds [id] + i. se) pr [i. fi]. pusb (id);
}
}
q. push (r1. se);
ckTopo [r1. se] = 1;
while (!q. empty ()) {
ll tmp = q. front ();
q. pop ();
topo. pusb (tmp);
for (ll i : pr [tmp]) if (!ckTopo [i]) {
q. push (i);
ch [i]. pusb (tmp);
ckTopo [i] = 1;
}
}
dijk (r2. fi, du);
dijk (r2. se, dv);
ll ans = du [r2. se];
// for (ll i : topo) cerr << i << ' '; cerr << '\n';
memset (du2, 0x3f, sizeof du2);
memset (dv2, 0x3f, sizeof dv2);
for (ll i : topo) {
mini (du2 [i], du [i]);
mini (dv2 [i], dv [i]);
for (ll j : pr [i]) {
mini (du2 [j], du2 [i]);
mini (dv2 [j], dv2 [i]);
}
mini (ans, du2 [i] + dv [i]);
mini (ans, dv2 [i] + du [i]);
// cerr << i << ' ' << min (du2 [i] + dv [i], dv2 [i] + du [i]) << '\n';
}
reverse (topo. begin (), topo. end ());
memset (du2, 0x3f, sizeof du2);
memset (dv2, 0x3f, sizeof dv2);
for (ll i : topo) {
mini (du2 [i], du [i]);
mini (dv2 [i], dv [i]);
for (ll j : ch [i]) {
mini (du2 [j], du2 [i]);
mini (dv2 [j], dv2 [i]);
}
mini (ans, du2 [i] + dv [i]);
mini (ans, dv2 [i] + du [i]);
// cerr << i << ' ' << min (du2 [i] + dv [i], dv2 [i] + du [i]) << '\n';
}
// forinc (i, 1, n) {
// cerr << i << ' ' << ds [i] << ' ' << du [i] << ' ' << dv [i] << ' ' << du2 [i] << ' ' << dv2 [i] << '\n';
// }
cout << ans;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// #define TASK "E:/Code/CP/task"
// if (fopen (TASK".inp", "r")) {
// freopen (TASK".inp", "r", stdin);
// freopen (TASK".out", "w", stdout);
// }
// cin >> t;
while (t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |