이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
struct GRAPH
{
int node;
long long weight;
};
struct DJK
{
int node;
long long weight;
bool operator < (const DJK & o) const
{
return weight > o.weight;
}
};
struct BT
{
int node;
long long weight;
};
bool visit[100100];
long long dis_s[100100], dis_u[100100], dis_v[100100];
vector<GRAPH> g[100100];
priority_queue<DJK> djk;
stack<BT> bt;
int main()
{
int n, m, s, t, u, v;
scanf(" %d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
while(m--)
{
int u, v;
long long w;
scanf(" %d %d %lld",&u,&v,&w);
g[u].pb({v, w});
g[v].pb({u, w});
}
for(int i=1 ; i<=n ; i++)
dis_s[i] = dis_u[i] = dis_v[i] = 1e15;
dis_s[s] = dis_u[u] = dis_v[v] = 0;
for(int i=1 ; i<=n ; i++)
visit[i] = false;
djk.push({s, 0});
while(!djk.empty())
{
int nown = djk.top().node;
long long noww = djk.top().weight;
djk.pop();
if(visit[nown]) continue ;
visit[nown] = true;
for(auto x : g[nown])
if(dis_s[x.node] > noww + x.weight)
{
dis_s[x.node] = noww + x.weight;
djk.push({x.node, dis_s[x.node]});
}
}
for(int i=1 ; i<=n ; i++)
visit[i] = false;
djk.push({u, 0});
while(!djk.empty())
{
int nown = djk.top().node;
long long noww = djk.top().weight;
djk.pop();
if(visit[nown]) continue ;
visit[nown] = true;
for(auto x : g[nown])
if(dis_u[x.node] > noww + x.weight)
{
dis_u[x.node] = noww + x.weight;
djk.push({x.node, dis_u[x.node]});
}
}
for(int i=1 ; i<=n ; i++)
visit[i] = false;
djk.push({v, 0});
while(!djk.empty())
{
int nown = djk.top().node;
long long noww = djk.top().weight;
djk.pop();
if(visit[nown]) continue ;
visit[nown] = true;
for(auto x : g[nown])
if(dis_v[x.node] > noww + x.weight)
{
dis_v[x.node] = noww + x.weight;
djk.push({x.node, dis_v[x.node]});
}
}
long long ans = 1e15;
// min v
bt.push({t, 1000000000000000});
while(!bt.empty())
{
int nown = bt.top().node;
long long noww = bt.top().weight;
bt.pop();
ans = min(ans, dis_u[nown] + noww);
for(auto x : g[nown])
if(dis_s[x.node] + x.weight == dis_s[nown])
bt.push({x.node, min(dis_v[x.node], noww)});
}
// min u
bt.push({t, 1000000000000000});
while(!bt.empty())
{
int nown = bt.top().node;
long long noww = bt.top().weight;
bt.pop();
ans = min(ans, dis_v[nown] + noww);
for(auto x : g[nown])
if(dis_s[x.node] + x.weight == dis_s[nown])
bt.push({x.node, min(dis_u[x.node], noww)});
}
printf("%lld\n",min(ans, dis_u[v]));
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
37 | scanf(" %d %d %d %d %d %d",&n,&m,&s,&t,&u,&v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
42 | scanf(" %d %d %lld",&u,&v,&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... |