이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define W while
#define int long long
using namespace std;
#define mp make_pair
const int N = 200005;
namespace SSSP {
struct edge {
int to,w;
edge *nex;
}*head[N];
void add(int u,int v,int w) {
edge *cur=new edge;
cur->to=v;
cur->w=w;
cur->nex=head[u];
head[u]=cur;
}
int vis[N];
priority_queue<pair<int,int>> q;
void dij(int s,int d[],size_t size) {
memset(vis,0,sizeof(vis));
memset(d,0x2f,size);
d[s]=0;
q.push(mp(-d[s],s));
W(!q.empty()) {
int u=q.top().second;
q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(edge *cur=head[u]; cur; cur=cur->nex) {
if(d[cur->to]>d[u]+cur->w) {
d[cur->to]=d[u]+cur->w;
q.push(mp(-d[cur->to],cur->to));
}
}
}
}
} using namespace SSSP;
void chmin(int &x,int y) {
x=min(x,y);
}
int du[N],dv[N],dt[N],ans;
namespace SSSP_EX {
int d[N],fu[N],fv[N];
priority_queue<pair<int,int>> q;
void dp(int s) {
memset(vis,0,sizeof(vis));
memset(d,0x2f,sizeof(d));
memset(fu,0x2f,sizeof(fu));
memset(fv,0x2f,sizeof(fv));
d[s]=0,fu[s]=du[s],ans=fu[s]+dv[s];
q.push(mp(-d[s],s));
fv[s]=dv[s];
W(!q.empty()) {
int u=q.top().second;
q.pop();
if(vis[u]) continue ;
vis[u]=1;
for(edge *cur=head[u]; cur; cur=cur->nex) {
if(d[cur->to]>d[u]+cur->w) {
fu[cur->to]=fv[cur->to]=0x2f2f2f2f2f2f2f2f;
d[cur->to]=d[u]+cur->w;
q.push(mp(-d[cur->to],cur->to));
}
if(d[cur->to]==d[u]+cur->w) {
chmin(fu[cur->to],du[cur->to]);
chmin(fu[cur->to],fu[u]);
chmin(fv[cur->to],dv[cur->to]);
chmin(fv[cur->to],fv[u]);
}
}
}
}
} using namespace SSSP_EX;
signed main() {
//7338696
ios::sync_with_stdio(0),cin.tie(0);
int n,m,s,t,u,v,i;
int x,y,z;
cin>>n>>m>>s>>t>>u>>v;
for(i=1; i<=m; i++) {
cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);
}
dij(u,du,sizeof du);
dij(t,dt,sizeof dt);
dij(v,dv,sizeof dv);
dp(s);
for(i=1; i<=n; i++) if(dt[s]==dt[i]+d[i]) chmin(ans,fu[i]+dv[i]);
for(i=1; i<=n; i++) {
if(dt[s]==dt[i]+d[i])
chmin(ans,fv[i]+du[i]);
}
chmin(ans,du[v]);
cout<<ans<<endl;
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... |