이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// In the name of Allah. Ya ali!
#include<bits/stdc++.h>
#define double long double
typedef long long ll;
const ll MAX_N = 1e5+10;
const ll MOD = 1e9+7;
using namespace std;
vector<pair<int,int>> g[MAX_N];
vector<int> p[MAX_N];
vector<int> pr[MAX_N];
ll dis[MAX_N];
ll m1[MAX_N];
ll d1[MAX_N];
ll d2[MAX_N];
ll m2[MAX_N];
int mark[MAX_N];
int n,m,s,t,u,v;
ll ans = 1e18;
void dij(int start)
{
for(int i = 1;i<=n;++i)
dis[i] = 1e18;
dis[start] = 0;
set<pair<ll,int>> st;
for(int i = 1;i<=n;++i)
st.insert({dis[i],i});
while(st.size())
{
int v = (*st.begin()).second;
st.erase(st.begin());
for(auto x:g[v])
{
int u = x.first;
ll d = dis[v]+x.second;
if (dis[u]==d)
p[u].push_back(v);
else if (dis[u]>d)
{
p[u].clear();
p[u].push_back(v);
st.erase({dis[u],u});
dis[u] = d;
st.insert({dis[u],u});
}
}
}
}
void bfs(int v)
{
vector<int> q;
q.push_back(v);
mark[v]++;
for(int i = 0;i<q.size();++i)
{
int u = q[i];
ans = min(ans,min(m1[u]+d2[u],m2[u]+d1[u]));
for(auto x:pr[u])
{
m1[x] = min(m1[x],m1[u]);
m2[x] = min(m2[x],m2[u]);
if (!mark[x])
{
q.push_back(x);
mark[x]++;
}
}
}
}
int main()
{
cin >> n >> m >> s >> t >> u >> v;
for(int i = 1;i<=m;++i)
{
int u,v,w;
cin >> u >> v >> w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
dij(s);
for(int i = 1;i<=n;++i)
pr[i] = p[i];
dij(u);
for(int i = 1;i<=n;++i)
d1[i] = m1[i] = dis[i];
dij(v);
for(int i = 1;i<=n;++i)
d2[i] = m2[i] = dis[i];
ans = dis[u];
bfs(t);
cout << ans;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
commuter_pass.cpp: In function 'void bfs(int)':
commuter_pass.cpp:56:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0;i<q.size();++i)
~^~~~~~~~~
# | 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... |