이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long
#define MAXN 100010
#define llinf 1e16
using namespace std;
vector<pair<ll,ll> > G[MAXN];
vector<ll> D[MAXN];
ll n,s,t,u,v,ds[MAXN],du[MAXN],dv[MAXN],dt[MAXN],ans,minu[MAXN],minv[MAXN];
void Dijkstra(ll st,ll *d)
{
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
for (ll i=1;i<=n;i++)
d[i]=llinf;
d[st]=0;
q.push({0,st});
while (!q.empty())
{
ll t=q.top().second,dt=q.top().first;
q.pop();
if (d[t]!=dt)
continue;
for (auto next : G[t])
{
ll i=next.first,c=next.second;
if (d[t]+c<d[i])
{
d[i]=d[t]+c;
q.push({d[i],i});
}
}
}
}
set<pair<ll,ll> > edges;
void DFS(ll i,ll p)
{
D[p].push_back(i);
for (auto next : G[i])
{
if (ds[i]+next.second+dt[next.first]==ds[t] && !edges.count({i,next.first}))
{
edges.insert({i,next.first});
DFS(next.first,i);
}
}
}
void Dijkstra_Solve()
{
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
for (ll i=1;i<=n;i++)
{
minu[i]=llinf;
minv[i]=llinf;
}
minu[s]=du[s];
minv[s]=dv[s];
q.push({minu[s],s});
while (!q.empty())
{
ll t=q.top().second,d=q.top().first;
q.pop();
if (minu[t]!=d)
continue;
ans=min(ans,minu[t]+minv[t]);
for (ll next : D[t])
{
if (minu[next]==llinf)
{
minu[next]=du[next];
minv[next]=dv[next];
q.push({minu[next],next});
}
if (minu[t]<minu[next])
{
minu[next]=minu[t];
minv[next]=min(dv[next],minv[t]);
q.push({minu[next],next});
continue;
}
if (minu[t]==minu[next] && minv[t]<minv[next])
{
minv[next]=minv[t];
q.push({minu[next],next});
continue;
}
}
}
for (ll i=1;i<=n;i++)
{
minu[i]=llinf;
minv[i]=llinf;
}
minu[s]=du[s];
minv[s]=dv[s];
q.push({minv[s],s});
while (!q.empty())
{
ll t=q.top().second,d=q.top().first;
q.pop();
if (minv[t]!=d)
continue;
ans=min(ans,minu[t]+minv[t]);
for (ll next : D[t])
{
if (minv[next]==llinf)
{
minu[next]=du[next];
minv[next]=dv[next];
q.push({minv[next],next});
}
if (minv[t]<minv[next])
{
minv[next]=minv[t];
minu[next]=min(du[next],minu[t]);
q.push({minv[next],next});
continue;
}
if (minv[t]==minv[next] && minu[t]<minu[next])
{
minu[next]=minu[t];
q.push({minu[next],next});
continue;
}
}
}
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
ll m,a,b,c;
cin >> n >> m;
cin >> s >> t >> u >> v;
for (ll i=1;i<=m;i++)
{
cin >> a >> b >> c;
G[a].push_back({b,c});
G[b].push_back({a,c});
}
Dijkstra(s,ds);
Dijkstra(u,du);
Dijkstra(v,dv);
Dijkstra(t,dt);
DFS(s,0);
ans=du[v];
Dijkstra_Solve();
cout << ans;
return 0;
}
# | 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... |