#include <bits/stdc++.h>
using namespace std;
// #include <tr2/dynamic_bitset>
// using custom_bitset = tr2::dynamic_bitset<>;
#define pb push_back
#define rbg(v) v.rbegin()
#define bg(v) v.begin()
#define all(v) v.begin(), v.end()
#define SZ(v) int(v.size())
#define MP make_pair
#define fi first
#define se second
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define for0(i, n) forn(i, 0, n - 1)
#define for1(i, n) forn(i, 1, n)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
#define far0(i, n) fora(i, n - 1, 0)
#define far1(i, n) fora(i, n, 1)
#define foru(i, v) for(auto & i : v)
#define fors(i, a, b, c) for(int i = a; i <= b; i += c)
#define lb lower_bound
#define ub upper_bound
#define ord1(s, n) s + 1, s + int(n) + 1
#define ord0(s, n) s, s + int(n)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(a) cout << #a << " = " << a << ", "
//#include <bits/extc++.h>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ost;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, bool> ib;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef vector<ll> vl;
typedef vector<ii> vii;
typedef vector<pll> vpll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<char> vc;
typedef long double ld;
typedef double db;
//typedef __int128 Int;
const int mod1 = 1e9 + 7;
const int mod2 = 998244353;
const ll INF = LLONG_MAX;
const int MX = 4e5;
void dijkstra(vvii & graph, vl & d, int s) {
d[s] = 0;
priority_queue<pli> pq;
pq.push({0, s});
while(!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
w = - w;
if(d[u] != w) continue;
for(auto & [v, w2] : graph[u]) {
if(d[v] <= w + w2) continue;
d[v] = w + w2;
pq.push({- w - w2, v});
}
}
}
void dpf(int u, vvi & dag, ll & ans, vpll & dp, vb & vis) {
if(vis[u]) return;
vis[u] = 1;
if(!SZ(dag[u]))
return;
pll best = {INF, INF};
foru(v, dag[u]) {
dpf(v, dag, ans, dp, vis);
best.fi = min(best.fi, dp[v].fi);
best.se = min(best.se, dp[v].se);
}
ans = min(ans, dp[u].fi + best.se);
ans = min(ans, dp[u].se + best.fi);
dp[u].fi = min(dp[u].fi, best.fi);
dp[u].se = min(dp[u].se, best.se);
}
void solve () {
int n, m, s, t, a, b;
cin >> n >> m >> s >> t >> a >> b;
-- s, -- t, -- a, -- b;
vl ds(n, INF), dt(n, INF), da(n, INF), db(n, INF);
vvii graph(n);
while(m --) {
int u, v, w;
cin >> u >> v >> w;
graph[-- u].pb({-- v, w});
graph[v].pb({u, w});
}
dijkstra(graph, ds, s);
dijkstra(graph, dt, t);
dijkstra(graph, da, a);
dijkstra(graph, db, b);
vvi dagst(n);
for0(u, n)
for(auto & [v, w] : graph[u]) {
if(ds[u] + dt[v] + w != ds[t]) continue;
dagst[u].pb(v);
}
vpll dp(n, {INF, INF});
for0(u, n)
dp[u] = {da[u], db[u]};
ll ans = da[b];
vb vis(n);
dpf(s, dagst, ans, dp, vis);
cout << ans;
}
int main ()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// freopen("palpath.out", "w", stdout);
// freopen("palpath.in", "r", stdin);
int t = 1;
// cin >> t;
for1(i, t){
//cout << "Case " << i << ": ";
solve();
cout << '\n';
}
return 0;
}
# | 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... |