이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define iii pair<int,ii>
#define vii vector<ii>
#define fi first
#define se second
#define endl '\n'
using namespace std;
const double eps = 0.000001;
const int mod = 1000000007;
const int N = 100001;
const int MATRIX_SIZE = 3;
int n,m,s,t,u,v,du[N],dv[N],ds[N],dpu[N],dpv[N];
vector <ii> G[N];
bool vi[N];
void Dijk(int x,int *dist){
fill(dist+1,dist+n+1,1e18);
dist[x]=0;
priority_queue <ii,vector <ii>, greater <ii>> xet;
xet.push({0,x});
while (xet.size()){
ii tam=xet.top();
xet.pop();
if (tam.fi>dist[tam.se]) continue;
for (auto htc:G[tam.se]){
if (dist[htc.fi]>htc.se+tam.fi){
// cout<<htc.fi<<' '<<htc.se<<' '<<tam.fi<<endl;
dist[htc.fi]=htc.se+tam.fi;
xet.push({dist[htc.fi],htc.fi});
}
}
}
// dist[0]=2;
}
void Dp(){
fill(ds+1,ds+n+1,1e18);
ds[s]=0;
fill(dpu,dpu+n+1,1e18);
fill(dpv,dpv+n+1,1e18);
dpu[s]=du[s];
dpv[s]=dv[s];
priority_queue <iii,vector <iii>,greater<iii>> xet;
xet.push({0,{s,0}});
while (xet.size()){
iii tam=xet.top();
int dist=tam.fi;
int node=tam.se.fi;
int par=tam.se.se;
xet.pop();
if (dist>ds[node]) continue;
if (dpu[node]+dpv[node]>min(dpu[par],du[node])+min(dpv[par],dv[node])){
dpu[node]=min(dpu[par],du[node]);
dpv[node]=min(dpv[par],dv[node]);
}
// cout<<node<<' '<<dpu[node]<<' '<<dpv[node]<<' '<<par<<endl;
if (!vi[node]){
vi[node]=true;
for (auto x:G[node]){
if (ds[x.fi]>=x.se+dist){
ds[x.fi]=x.se+dist;
xet.push({ds[x.fi],{x.fi,node}});
}
}
}
}
}
void solve(){
cin>>n>>m>>s>>t>>u>>v;
for (int i=1,s1,s2,s3;i<=m;++i){
cin>>s1>>s2>>s3;
G[s2].push_back({s1,s3});
G[s1].push_back({s2,s3});
}
Dijk(u,du);
Dijk(v,dv);
// cout<<du[3];
// swap(t,s);
Dp();
cout<<min(dpu[t]+dpv[t],du[v]);
}
main() {
//freopen("ok.inp","r",stdin);
//freopen("ok.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
solve();
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp:83:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
83 | 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... |