이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll,ll>
const ll maxn=2e5+2,inf=1e16;
int n,m,s,t,op,ed;
vector<ll> d1,d2,t1,t2;
vector<ii> adj[maxn];
vector<ll> g[maxn];
vector<int> ver;
bool ok[maxn];
bool pass[maxn];
ll ans=inf;
ll dp[maxn];
void dij(int st, vector<ll> &dis){
dis.resize(n+2,inf);
priority_queue <ii,vector<ii>,greater<ii>> pq;
pq.push({0,st});
dis[st]=0;
while(!pq.empty()){
int u=pq.top().se;
int d=pq.top().fi;
pq.pop();
if (dis[u]<d) continue;
for (ii v:adj[u]){
if (dis[v.fi]>dis[u]+v.se){
dis[v.fi]=dis[u]+v.se;
pq.push({dis[v.fi],v.fi});
}
}
}
}
void dfs(int u){
for (int v: g[u]){
if (pass[v]){
dp[v]=min(dp[u],t2[v]);
}else{
pass[v]=1;
dfs(v);
}
}
}
int main(){
cin>>n>>m>>s>>t>>op>>ed;
while (m--){
int a,b,c; cin>>a>>b>>c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
dij(s,d1);
dij(t,d2);
dij(op,t1);
dij(ed,t2);
for (int i=1;i<=n;++i){
dp[i]=inf;
if (d1[i]+d2[i] == d1[t]){
ver.push_back(i);
ok[i]=1;
}
}
if (s==op){
for (int i:ver){
ans=min(ans,t2[i]);
}
cout<<ans;
return 0;
}
for (int i: ver){
for (ii x: adj[i]) if (ok[x.fi]) g[i].push_back(x.fi);
}
/*ll sna=inf;
for (int i:ver){
ans=min(ans,t1[i]);
sna=min(sna,t2[i]);
}
cout<<min(ans+sna,t1[ed]);
/*queue<ii> qu;
qu.push({s,s});
pass[s]=1;
while (!qu.empty()){
int u=qu.front().fi;
int p=qu.front().se;
//cout<<u<<endl;
qu.pop();
dp[u]=min(dp[p],t2[u]);
for (int v: g[u]){
dp[v]=min(dp[u],t2[v]);
if (pass[v]==0){
pass[v]=1;
qu.push({v,u});
}
}
}*/
dp[s]=t2[s];
pass[s]=1;
dfs(s);
for (int u:ver) ans=min(ans,t1[u]+dp[u]);
//for (int i:ver) cout<<i<<" "<<dp[i]<<endl;
cout<<min(ans,t1[ed]);
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp:83:5: warning: "/*" within comment [-Wcomment]
83 | /*queue<ii> qu;
|
# | 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... |