This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 10;
const ll mod = 998244353;
ll um(ll a, ll b){
return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
return ((1LL * a - b) % mod + mod) % mod;
}
ll n, m, from, to, fir, sec;
ll d[N], used[N];
vector <pll> q[N];
void dfs(int v){
used[v] = true;
for(auto u : q[v]){
if(used[u.F]) continue;
if(d[u.F] + u.S == d[v]) dfs(u.F);
}
}
ll d1[N][2];
void create(){
d[from] = 0;
set <pll> st;
st.insert({d[from], from});
while((ll)st.size() != 0){
auto [place, v] = *st.begin();
st.erase(st.begin());
if(d[v] != place) continue;
for(auto u : q[v]){
if(d[u.F] == -1 || d[u.F] > d[v] + u.S){
d[u.F] = d[v] + u.S;
st.insert({d[u.F], u.F});
}
}
}
}
set <pair <pll, pll>> st;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
//freopen("bank.in", "r", stdin);
//freopen("bank.out", "w", stdout);
cin >> n >> m >> from >> to >> fir >> sec;
for(ll i = 0, a, b, c; i < m; i++){
cin >> a >> b >> c;
q[a].pb({b, c});
q[b].pb({a, c});
}
for(ll i = 1; i <= n; i++){
d[i] = -1;
d1[i][0] = d1[i][1] = -1;
}
create();
dfs(to);
d1[fir][0] = 0;
st.insert({{0, fir}, {0, 0}});
if(used[fir]){
d1[fir][1] = 0;
st.insert({{0, fir}, {1, 1}});
st.insert({{0, fir}, {1, -1}});
}
while((ll)st.size() != 0){
auto [f, s] = *st.begin();
auto [place, v] = f;
auto [was, dir] = s;
st.erase(st.begin());
if(place != d1[v][was]) continue;
for(auto u : q[v]){
if(dir != 0){
if(used[u.F] && d[v] + dir * u.S == d[u.F]){
if(d1[v][1] < d1[u.F][1] || d1[u.F][1] == -1){
d1[u.F][1] = d1[v][1];
st.insert({{d1[u.F][1], u.F}, {1, dir}});
}
}
} else{
if(was == 0 && used[u.F]){
if(d1[v][0] + u.S < d1[u.F][1] || d1[u.F][1] == -1){
d1[u.F][1] = d1[v][0] + u.S;
st.insert({{d1[u.F][1], u.F}, {1, -1}});
st.insert({{d1[u.F][1], u.F}, {1, 1}});
}
}
}
if(d1[v][was] + u.S < d1[u.F][was] || d1[u.F][was] == -1){
d1[u.F][was] = d1[v][was] + u.S;
st.insert({{d1[u.F][was], u.F}, {was, 0}});
}
}
}
cout << min(d1[sec][0], d1[sec][1]);
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... |