이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct A{
long long a,w,p;
bool operator<(const A& o)const{
return w>o.w;
}
};
long long ans;
vector<vector<long long>> dis(2,vector<long long>(N,1e18));
vector<A> g[N];
priority_queue<A> q;
bitset<N> vis;
void dijk(int idx,int s){
q.push({s,0});
dis[idx][s]=0;
while(!q.empty()){
auto [a,w,p]=q.top();
q.pop();
if(w>dis[idx][a])continue;
for(auto x:g[a]){
if(w+x.w<dis[idx][x.a])q.push({x.a,w+x.w}),dis[idx][x.a]=w+x.w;
}
}
}
void dijk2(int s,int e){
vector<long long> diss(N,1e18);
vector<vector<long long>> dp(2,vector<long long>(N,1e18));
vis=0;
q.push({s,0,0});
while(!q.empty()){
auto [a,w,p]=q.top();
q.pop();
if(!vis[a]){
vis[a]=true;
diss[a]=w;
dp[0][a]=min(dis[0][a],dp[0][p]);
dp[1][a]=min(dis[1][a],dp[1][p]);
for(auto x:g[a])q.push({x.a,w+x.w,a});
}
else if(w==diss[a]&&min(dis[0][a],dp[0][p])+min(dis[1][a],dp[1][p])<dp[0][a]+dp[1][a])dp[0][a]=min(dis[0][a],dp[0][p]),dp[1][a]=min(dis[1][a],dp[1][p]);
}
ans=min(ans,dp[0][e]+dp[1][e]);
}
int main(){
int n,m,s,t,u,v,i,a,b;
long long w,mi;
scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
for(i=1;i<=m;i++){
scanf("%d %d %lld",&a,&b,&w);
g[a].push_back({b,w});
g[b].push_back({a,w});
}
dijk(0,u);
dijk(1,v);
ans=dis[0][v];
dijk2(s,t);
dijk2(t,s);
printf("%lld",ans);
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:53:17: warning: unused variable 'mi' [-Wunused-variable]
53 | long long w,mi;
| ^~
commuter_pass.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d %d %lld",&a,&b,&w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | 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... |