이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int> > adj[100002];
int dis[100002];
int dit[100002];
int ans[100002][4];
priority_queue<tuple<int,int>,vector<tuple<int,int> > , greater<tuple<int,int> > > pq;
priority_queue<tuple<int,int,int>,vector<tuple<int,int,int> > ,greater<tuple<int,int,int> > > last;
int n,m,s,t,u,v;
void djikstra(){
while(!pq.empty()){
auto [dist,idx]=pq.top();
pq.pop();
if(dist!=dis[idx])continue;
for(auto r : adj[idx]){
if(dis[r.first]>dist+r.second){
dis[r.first]=dist+r.second;
pq.push({dis[r.first],r.first});
}
}
}
}
void djikstra2(){
while(!pq.empty()){
auto [dist,idx]=pq.top();
pq.pop();
if(dist!=dit[idx])continue;
for(auto r : adj[idx]){
if(dit[r.first]>dist+r.second){
dit[r.first]=dist+r.second;
pq.push({dit[r.first],r.first});
}
}
}
}
void jawab(){
while(!last.empty()){
auto [dist,idx,type]=last.top();
last.pop();
if(dist!=ans[idx][type])continue;
if(type==0){
for(auto r : adj[idx]){
if(ans[r.first][0]>dist+r.second){
ans[r.first][0]=dist+r.second;
last.push({ans[r.first][0],r.first,0});
//cout<<r.first<<" "<<ans[r.first][0]<<" "<<0<<endl;
}
if(ans[r.first][1]>dist && dit[idx]+dis[r.first]+r.second==dis[t]){
ans[r.first][1]=dist;
last.push({ans[r.first][1],r.first,1});
//cout<<r.first<<" "<<ans[r.first][1]<<" "<<1<<endl;
}
if(ans[r.first][2]>dist && dis[idx]+dit[r.first]+r.second==dis[t]){
ans[r.first][2]=dist;
last.push({ans[r.first][2],r.first,2});
//cout<<r.first<<" "<<ans[r.first][2]<<" "<<2<<endl;
}
}
}
else if(type==1){
for(auto r : adj[idx]){
if(ans[r.first][1]>dist && dit[idx]+dis[r.first]+r.second==dis[t]){
ans[r.first][1]=dist;
last.push({ans[r.first][1],r.first,1});
// cout<<r.first<<" "<<ans[r.first][1]<<" "<<1<<endl;
}
}
for(auto r : adj[idx]){
if(ans[r.first][3]>dist+r.second){
ans[r.first][3]=dist+r.second;
last.push({ans[r.first][3],r.first,3});
}
}
}
else if(type==2){
for(auto r : adj[idx]){
if(ans[r.first][2]>dist && dis[idx]+dit[r.first]+r.second==dis[t]){
ans[r.first][2]=dist;
last.push({ans[r.first][2],r.first,2});
}
}
for(auto r : adj[idx]){
if(ans[r.first][3]>dist+r.second){
ans[r.first][3]=dist+r.second;
last.push({ans[r.first][3],r.first,3});
}
}
}
else if(type==3){
for(auto r : adj[idx]){
if(ans[r.first][3]>dist+r.second){
ans[r.first][3]=dist+r.second;
last.push({ans[r.first][3],r.first,3});
}
}
}
}
}
signed main(){
cin>>n>>m>>s>>t>>u>>v;
for(int q=1;q<=m;q++){
int a,b,w;
cin>>a>>b>>w;
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
for(int q=1;q<=n;q++){
ans[q][0]=ans[q][1]=ans[q][2]=ans[q][3]=dis[q]=dit[q]=1e18;
}
pq.push({0,s});
dis[s]=0;
djikstra();
pq.push({0,t});
dit[t]=0;
djikstra2();
ans[u][0]=0;
last.push({0,u,0});
jawab();
int maks=1e18;
for(int q=0;q<=3;q++){
maks=min(maks,ans[v][q]);
}
cout<<maks<<endl;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void djikstra()':
commuter_pass.cpp:14:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
14 | auto [dist,idx]=pq.top();
| ^
commuter_pass.cpp: In function 'void djikstra2()':
commuter_pass.cpp:29:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
29 | auto [dist,idx]=pq.top();
| ^
commuter_pass.cpp: In function 'void jawab()':
commuter_pass.cpp:44:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
44 | auto [dist,idx,type]=last.top();
| ^
# | 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... |