#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
//data structures
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef vector<ll> vi;
typedef vector<string> vs;
typedef vector<vector<ll>> vvi;
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define sz(a) ((ll)a.size())
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
#define fro front
#define pqueue priority_queue
#define ubound upper_bound
#define lbound lower_bound
#define beg(v) v.begin()
//bit operations
ll flip(ll x){
return ~(x) ^ (1 << 32);
}
ll allon(ll x){
return (1LL << x) - 1;
}
bool bit(ll a, ll i){
return (1LL << i) & a;
}
#define llpc(x) __builtin_popcountll(x)
#define ipc(x) __builtin_popcount(x)
#define iclz(x) __builtin_clz(x)
#define llclz(x) __builtin_clzll(x)
#define ictz(x) __builtin_ctz(x)
#define llctz(x) __builtin_ctzll(x)
//answers
#define cYES cout << "YES" << endl
#define cYes cout << "Yes" << endl
#define cyes cout << "yes" << endl
#define cNO cout << "NO" << endl
#define cNo cout << "No" << endl
#define cno cout << "no" << endl
#define ipsb cout << -1 << endl
const ll mod2 = 998244353;
const ll mod = 1000000007;
const ll inf = ll(1e18);
// read arr vec matr etc
#define fill(x, y) memset(x, y, sizeof(x))
void read(vector<auto> &x){
for(auto &e:x) cin >> e;
}
void mread(vector<vector<ll>> &p, ll nnn, ll mmm){
for(ll i = 0; i < nnn; ++i){
vector<ll> pp;
for(ll j = 0; j < mmm; ++j){
ll wq; cin >> wq; pp.pb(wq);
}
p.pb(pp);
}
}
// Solution
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
ll n, m; cin >> n >> m;
ll s, t; cin >> s >> t;
ll a, b; cin >> a >> b;
vector<vii> x(n+1);
for(ll i = 0; i < m; ++i){
ll u, v; cin >> u >> v;
ll cost; cin >> cost;
x[u].pb({v, cost});
x[v].pb({u, cost});
}
ll pass[n+1];
ll dist[n+1];
ll dis[n+1];
for(ll i = 0; i <= n; ++i){
dis[i] = inf;
dist[i] = inf;
pass[i] = inf;
}
pqueue<pair<ll, ii>, vector<pair<ll, ii>>, greater<pair<ll, ii>>> q;
q.push({0, {s, s}});
pass[s] = 0;
ll fat[n+1];
vvi child(n+1);
vvi fats(n+1);
fill(fat, 0);
int vi[n+1];
fill(vi, 0);
while(sz(q)){
ll no = q.top().se.se;
ll fa = q.top().se.fi;
ll cost = q.top().fi;
q.pop();
if(pass[no] != cost){
continue;
}
fat[no]++;
fats[no].pb(fa);
if(vi[no])continue;
vi[no] = 1;
for(auto e:x[no]){
ll ncost = cost + e.se;
if(pass[e.fi] >= ncost){
pass[e.fi] = ncost;
q.push({ncost, {no, e.fi}});
}
}
}
queue<ll> bfs;
bfs.push(t);
while(sz(bfs)){
ll no = bfs.fro();
bfs.pop();
if(vi[no] == 3)continue;
vi[no] = 3;
for(auto e:fats[no]){
child[e].pb(no);
if(vi[e] <= 1){
vi[e] = 2;
bfs.push(e);
}
}
}
pqueue<ii, vii, greater<ii>> pq;
pq.push({0, a});
dist[a] = 0;
while(sz(pq)){
ll no = pq.top().se;
ll cost = pq.top().fi;
pq.pop();
if(dist[no] != cost){
continue;
}
for(auto e:x[no]){
ll ncost = cost + e.se;
if(ncost < dist[e.fi]){
dist[e.fi] = ncost;
pq.push({ncost, e.fi});
}
}
}
//cout << "work" << endl;
pq.push({0, b});
dis[b] = 0;
while(sz(pq)){
ll no = pq.top().se;
ll cost = pq.top().fi;
pq.pop();
if(dis[no] != cost){
continue;
}
for(auto e:x[no]){
ll ncost = cost + e.se;
if(ncost < dis[e.fi]){
dis[e.fi] = ncost;
pq.push({ncost, e.fi});
}
}
}
ll ans = dist[b];
ll dpa[n+1];
ll dpb[n+1];
ll dpma[n+1];
ll dpmb[n+1];
for(ll i = 0; i <= n; ++i){
dpa[i] = inf;
dpb[i] = inf;
dpma[i] = inf;
dpmb[i] = inf;
}
bfs.push(s);
dpa[s] = dist[s];
dpb[s] = dis[s];
dpma[s] = dpa[s];
dpmb[s] = dpb[s];
ll vis[n+1];
fill(vis, 0);
while(sz(bfs)){
ll no = bfs.fro();
bfs.pop();
if(vis[no]){
continue;
}
vis[no] = 1;
for(auto e:child[no]){
fat[e]--;
if(fat[e] == 0){
bfs.push(e);
}
}
ll newa = dist[no];
ll newb = dis[no];
ll an = newa + newb;
dpa[no] = newa;
dpb[no] = newb;
dpma[no] = dpa[no];
dpmb[no] = dpb[no];
for(auto e:fats[no]){
dpma[no] = min(dpma[no], dpma[e]);
dpmb[no] = min(dpmb[no], dpmb[e]);
ll nan = inf;
nan = min(nan, dpma[no] + newb);
if(nan < an){
dpa[no] = dpma[no];
dpb[no] = newb;
an = nan;
}
nan = min(nan, dpmb[no] + newa);
if(nan < an){
dpa[no] = newa;
dpb[no] = dpmb[no];
an = nan;
}
}
}
for(ll i = 0; i <= n; ++i){
ans = min(ans, dpa[i] + dpb[i]);
//cout << ans << " " << i << endl;
}
cout << ans << endl;
}
Compilation message (stderr)
commuter_pass.cpp: In function 'll flip(ll)':
commuter_pass.cpp:38:22: warning: left shift count >= width of type [-Wshift-count-overflow]
38 | return ~(x) ^ (1 << 32);
| ~~^~~~~
# | 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... |