이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define X first
#define Y second
#define ll long long
ll n,m,S,T,U,V,a,b,c,disu[100005],disv[100005],dp[100005],ans=1e18,d[100005],u,node,cost,y;
ll dp2[100005],d2[100005],w;
vector<pair<ll,ll> > v[100005];
priority_queue<pair<ll,ll> > pq;
void dij(ll st,ll dis[])
{
for(int i=1;i<=n;i++)dis[i]=1e18;
dis[st]=0;
pq.push({0,st});
while(!pq.empty())
{
u=pq.top().Y;
w=-pq.top().X;
if(w>dis[u])continue;
pq.pop();
if(v[u].size()>0)
for(int i=0;i<v[u].size();i++)
{
node=v[u][i].X,cost=v[u][i].Y;
if(dis[u]+cost<dis[node])
{
dis[node]=dis[u]+cost;
pq.push({-dis[node],node});
}
}
}
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&S,&T,&U,&V);
for(int i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
v[a].pb({b,c});
v[b].pb({a,c});
}
dij(U,disu),dij(V,disv);
for(int i=1;i<=n;i++)dp[i]=1e18,d[i]=1e18,d2[i]=1e18,dp2[i]=1e18;
dp[S]=disu[S],d[S]=0;
ans=min(ans,disu[S]+disv[S]);
pq.push({-d[S],S});
while(!pq.empty())
{
u=pq.top().Y;
w=-pq.top().X;
pq.pop();
if(w>d[u])continue;
if(v[u].size()>0)
for(int i=0;i<v[u].size();i++)
{
y=v[u][i].X,cost=v[u][i].Y;
if(d[u]+cost<d[y])
{
d[y]=d[u]+cost;
dp[y]=min(dp[y],min(dp[u],disu[y]));
pq.push({-d[y],y});
}
if(d[u]+cost==d[y])dp[y]=min(dp[y],min(dp[u],disu[y]));
}
}
dp2[T]=disu[T],d2[T]=0;
ans=min(ans,disu[T]+disv[T]);
pq.push({-d2[T],T});
while(!pq.empty())
{
u=pq.top().Y;
w=-pq.top().X;
pq.pop();
if(w>d2[u])continue;
if(v[u].size()>0)
for(int i=0;i<v[u].size();i++)
{
y=v[u][i].X,cost=v[u][i].Y;
if(d2[u]+cost<d2[y])
{
d2[y]=d2[u]+cost;
dp2[y]=min(dp2[y],min(dp2[u],disu[y]));
pq.push({-d2[y],y});
}
if(d2[u]+cost==d2[y])dp2[y]=min(dp2[y],min(dp2[u],disu[y]));
}
}
for(int i=1;i<=n;i++)
{
if(d[i]+d2[i]==d[T])
{
ans=min(ans,min(dp[i],dp2[i])+disv[i]);
}
}
ans=min(ans,disv[U]);
printf("%lld\n",ans);
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void dij(long long int, long long int*)':
commuter_pass.cpp:23:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
commuter_pass.cpp:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int i=0;i<v[u].size();i++)
| ~^~~~~~~~~~~~
commuter_pass.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&S,&T,&U,&V);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
39 | scanf("%lld%lld%lld",&a,&b,&c);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |