이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll
int n, m, S, T, U, V;
int Ds[100010], Du[100010], Dt[100010], Dv[100010];
bool v[100010];
vector<pii> g[100010];
pair<int ,pii> e[200010];
vector<pii> g2[100010];
void dijkstra(int s, vector<pii> g[], int D[], bool v[]){
multiset<pii> ms;
ms.insert({0, s});
D[s]=0;
while(!ms.empty()){
pii pr=(*ms.begin()); ms.erase(ms.begin());
int node=pr.sc, d=pr.ft;
v[node]=true;
for(pii pr:g[node]){
int u=pr.ft, c=pr.sc;
if(!v[u]){
auto it=ms.find({D[u], u});
if(it==ms.end()){
D[u]=d+c;
ms.insert({D[u], u});
}
else{
if((d+c)<D[u]){
D[u]=d+c;
ms.erase(it);
ms.insert({D[u], u});
}
}
}
}
}
for(int i=1; i<=n;i++){
v[i]=false;
}
}
void build_g2(){
for(int i=1; i<=m; i++){
int u=e[i].sc.ft, v=e[i].sc.sc, c=e[i].ft;
if( (Ds[u]+c+Dt[v])==Ds[T] ){
g2[u].pb({v, c});
}
if( (Ds[v]+c+Dt[u])==Ds[T] ){
g2[v].pb({u, c});
}
}
}
int res=1e18;
int mnu[100010], mnv[100010];
int dfsu(int s){
int dv=Dv[s];
v[s]=true;
for(pii pr:g2[s]){
int u=pr.ft;
dv=min(dv, Dv[u]);
if(!v[u]){
dv=min(dfsu(u), dv);}
dv=min(dv, mnv[u]);
}
res=min(res, Du[s]+dv);
mnv[s]=dv;
return dv;
}
int dfsv(int s){
int du=Du[s];
v[s]=true;
for(pii pr:g2[s]){
int u=pr.ft;
du=min(du, Du[u]);
if(!v[u]){
du=min(dfsv(u), du);}
du=min(du, mnu[u]);
}
res=min(res, du+Dv[s]);
mnu[s]=du;
return du;
}
int32_t main(){
INIT
cin>>n>>m;
cin>>S>>T;
cin>>U>>V;
for(int i=1; i<=m; i++){
int u, v, c;
cin>>u>>v>>c;
g[u].pb({v, c});
g[v].pb({u, c});
e[i]={c, {u, v}};
}
dijkstra(S, g, Ds, v);
dijkstra(T, g, Dt, v);
dijkstra(U, g, Du, v);
dijkstra(V, g, Dv, v);
build_g2();
dfsu(S);
for(int i=1; i<=n; i++){
v[i]=false;
}
dfsv(S);
cout<<min(res, Du[V]);
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... |