이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define ip pair<int,ii>
#define fi first
#define se second
const int maxn=1e5+7;
const int inf=1e15+7;
int vst[maxn];
int du[maxn];
int dv[maxn];
int ds[maxn];
int n,m,s,t,u,v;
int ans;
vector<ii>a[maxn];
int d[2][maxn];
void dijkstra1(int start,int arr[])
{
for(int i=1;i<=n;i++){vst[i]=0;arr[i]=inf;}
priority_queue<ii,vector<ii>,greater<ii>>q;
arr[start]=0;
q.push({0,start});
while(q.size()){
int u=q.top().se;
int du=q.top().fi;
q.pop();
if(vst[u])continue;
vst[u]=1;
for(ii p:a[u]){
int v=p.fi;
int w=p.se;
if(arr[v]>arr[u]+w){
arr[v]=arr[u]+w;
q.push({arr[v],v});
}
}
}
}
void dijkstra2(int start,int endd)
{
for(int i=0;i<=n;i++){
d[0][i]=inf;
d[1][i]=inf;
ds[i]=inf;
vst[i]=0;
}
ds[start]=0;
priority_queue<ip,vector<ip>,greater<ip>>q;
q.push(make_pair(0,make_pair(start,0)));
while(q.size()){
int node=q.top().se.fi;
int par=q.top().se.se;
int dnode=q.top().fi;
q.pop();
if(vst[node]==0){
vst[node]=1;
d[0][node]=min(du[node],d[0][par]);
d[1][node]=min(dv[node],d[1][par]);
ds[node]=dnode;
for(ii p:a[node]){
int v=p.fi;
int w=p.se;
q.push(make_pair(dnode+w,make_pair(v,node)));
}
}
else if(dnode==ds[node]){
if(min(du[node],d[0][par])+min(dv[node],d[1][par])<=d[0][node]+d[1][node])
{
d[0][node]=min(d[0][par],du[node]);
d[1][node]=min(d[1][par],dv[node]);
}
}
}
ans=min(ans,d[0][endd]+d[1][endd]);
}
main()
{
cin>>n>>m;
cin>>s>>t;
cin>>u>>v;
for(int i=1;i<=m;i++){
int x,y,w;
cin>>x>>y>>w;
a[x].push_back({y,w});
a[y].push_back({x,w});
}
dijkstra1(u,du);
dijkstra1(v,dv);
ans=du[v];
dijkstra2(s,t);
dijkstra2(t,s);
cout<<ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dijkstra1(long long int, long long int*)':
commuter_pass.cpp:27:13: warning: unused variable 'du' [-Wunused-variable]
27 | int du=q.top().fi;
| ^~
commuter_pass.cpp: At global scope:
commuter_pass.cpp:80:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
80 | main()
| ^~~~
# | 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... |