이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
/*
STAY ORGANIZED
CHANGE YOUR APPROACH
BE CONFIDENT
WA , WHATEVER STAY CALM
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
typedef long double ld ;
#define FAST ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define pb push_back
#define pi pair<ll,ll>
#define pll pair<ll,ll>
#define yes cout<<"YES"<<endl;
#define no cout<<"NO"<<endl;
#define flag cout<<"hi"<<endl;
#define fr(i,a,b) for(ll i = a;i < (ll)b;i++)
#define rfr(i,a,b) for(ll i = a;i > (ll)b;i--)
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define alll(x) ((x).begin()+1), (x).end()
#define MOD mod
#define endl '\n'
const ll mod = 1e9+7 ;
void io(){ios::sync_with_stdio(false) ;cin.tie(NULL) ;//freopen("grader.in.4","r",stdin) ;freopen("grader.out.4","w",stdout) ;
}
void dbg(vector<ll> tab){for(auto it : tab) cout<<it<<" ";cout<<endl;}
void dbgg(pi p){cout<<p.F<<" "<<p.S<<endl;}
void dbgpi(vector<pi> tab){for(auto it : tab) dbgg(it) ;}
template<class T> bool ckmax(T& a, const T& b){return a < b ? a = b, 1 : 0;}
template<class T> bool ckmin(T& a, const T& b){return a > b ? a = b, 1 : 0;}
template<class T> void add(T& a, const T& b){a = a + b ; if(a>mod) a-= mod ;}
void nop(){cout<<-1<<endl;return;}
const ll N = 1e5 +5 ;
const ll inf = 1e17 ;
ll n , m , x , y , s , t ;
vector<pi> v[N] ;
vector<ll> dag[N] ;
map<ll , bool> aded[N] ;
ll distf[N][5] ;
void dijkstra(ll source ,ll k)
{
for(ll i = 1 ; i<=n ; i++){
distf[i][k] = inf ;
}
distf[source][k] = 0 ;
priority_queue<pi , vector<pi> , greater<pi>> pq ;
vector<ll> vis(n+1 , 0) ;
distf[source][k] = 0 ;
pq.push({0 , source}) ;
while(!pq.empty()){
auto [d , node] = pq.top() ;
pq.pop() ;
if(vis[node]) continue ;
vis[node] = 1 ;
for(auto [to , w] : v[node]){
if(w + d < distf[to][k]){
distf[to][k] = w + d ;
pq.push({distf[to][k] , to}) ;
}
}
}
}
void solve()
{
cin>>n>>m>>s>>t>>x>>y ;
for(ll i = 1 ; i<=m ; i++){
ll from , to , weight ;
cin>>from>>to>>weight ;
v[from].pb({to , weight}) ;
v[to].pb({from , weight}) ;
}
priority_queue<array<ll,3> , vector<array<ll,3>> , greater<array<ll,3>>> pq ;
vector<ll> dist(n+1 , inf) ;
vector<ll> vis(n+1 , 0) , ind(n+1,0) ;
dist[s] = 0 ;
pq.push({0 , s , 0}) ;
while(!pq.empty()){
auto a = pq.top() ;
ll d = a[0] , node = a[1] , par = a[2] ;
pq.pop() ;
if(vis[node]){
if(d == dist[node] && node!=s){
dag[par].pb(node) ;
ind[node]++ ;
}
continue ;
}
vis[node] = 1 ;
if(node!= s){
dag[par].pb(node) ;
ind[node]++ ;
}
for(auto [to , w] : v[node]){
if(w + d <= dist[to]){
dist[to] = w + d ;
pq.push({dist[to] , to , node}) ;
}
}
}
dijkstra(x , 1) ;
dijkstra(y , 2) ;
queue<ll> q ;
vector<ll> order ;
for(ll i = 1 ; i<=n ; i++){
if(!ind[i]) q.push(i) ;
}
while(!q.empty()){
ll node = q.front() ;
q.pop() ;
order.pb(node) ;
for(auto it : dag[node]){
ind[it]-- ;
if(!ind[it]) q.push(it) ;
}
}
vector<ll> dist1(n+1 , inf) , dist2(n+1 , inf) ;
for(ll node : order){
dist1[node] = min(dist1[node] , distf[node][1]) ;
dist2[node] = min(dist2[node] , distf[node][2]) ;
for(auto to : dag[node]){
if(min(dist1[node] , distf[to][1]) + min(dist2[node] , distf[to][2]) <dist1[to] + dist2[to] ){
dist1[to] = min(dist1[node] , distf[to][1]) ;
dist2[to] = min(dist2[node] , distf[to][2]) ;
}
}
}
cout<<min(distf[y][1] , dist1[t] + dist2[t])<<endl;
}
int main()
{
/*
UNORDERED MAP IS SHIT
NEVER USE IT AGAIN
*/
io() ;
ll tt = 1 ;
// cin>>tt ;
while(tt--) solve() ;
return 0 ;
}
/*
!!!
ARRAY BOUNDS
OVERFLOW
UNORDERED MAP
CEIL DIV ON NEGATIVES
*/
# | 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... |