This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
inline namespace
{
} // namespace
void solve()
{
int n, m;
cin >> n >> m;
int s, t, u, v;
cin >> s >> t >> u >> v, --s, --t, --u, --v;
// cerr << s << ' ' << t << '\n';
// cerr << u << ' ' << v << '\n';
// swap(u, v);
vector<vector<pair<int, long>>> adj(n);
for (int i = 0; i < m; i++)
{
int a, b;
long c;
cin >> a >> b >> c, --a, --b;
adj[a].emplace_back(b, c);
adj[b].emplace_back(a, c);
}
vector<vector<int>> gr(n);
{
vector<long> dist(n, LONG_MAX);
priority_queue<pair<long, int>> pq;
vector<vector<int>> gr1(n);
vector<vector<int>> todo(n);
dist[s] = 0;
for (pq.emplace(-dist[s], s); !pq.empty();)
{
auto [d, a] = pq.top();
pq.pop();
if (d != -dist[a])
continue;
for (int b : todo[a])
gr1[a].push_back(b);
for (auto [b, c] : adj[a])
{
if (dist[a] + c < dist[b])
{
todo[b].clear(),
todo[b].push_back(a);
dist[b] = dist[a] + c;
pq.emplace(-dist[b], b);
}
else if (dist[a] + c == dist[b])
todo[b].push_back(a);
}
}
queue<int> q;
vector<bool> done(n, 0);
for (q.push(t); !q.empty();)
{
int a = q.front();
q.pop();
if (done[a])
continue;
done[a] = 1;
for (int b : gr1[a])
{
gr[b].push_back(a);
q.push(b);
}
}
}
long res = LONG_MAX;
{
vector<long> dist_u(n, LONG_MAX), dist_v(n, LONG_MAX);
{
priority_queue<pair<long, int>> pq;
dist_u[u] = 0;
for (pq.emplace(-dist_u[u], u); !pq.empty();)
{
auto [d, a] = pq.top();
pq.pop();
if (d != -dist_u[a])
continue;
for (auto [b, c] : adj[a])
{
if (dist_u[a] + c < dist_u[b])
{
dist_u[b] = dist_u[a] + c;
pq.emplace(-dist_u[b], b);
}
}
}
}
{
priority_queue<pair<long, int>> pq;
dist_v[v] = 0;
for (pq.emplace(-dist_v[v], v); !pq.empty();)
{
auto [d, a] = pq.top();
pq.pop();
if (d != -dist_v[a])
continue;
for (auto [b, c] : adj[a])
{
if (dist_v[a] + c < dist_v[b])
{
dist_v[b] = dist_v[a] + c;
pq.emplace(-dist_v[b], b);
}
}
}
}
res = dist_u[v];
vector<int> deg(n);
for (int i = 0; i < n; i++)
{
for (int j : gr[i])
deg[j]++;
}
queue<int> q;
vector<long> dp_u = dist_u, dp_v = dist_v;
for (q.push(s); !q.empty();)
{
int a = q.front();
q.pop();
// cerr << a << ' ' << dist_u[a] << '\n';
for (int b : gr[a])
{
dp_u[b] = min(dist_u[b], dp_u[a]),
dp_v[b] = min(dist_v[b], dp_v[a]);
res = min(res, dp_u[b] + dp_v[b]);
if (--deg[b] == 0)
q.push(b);
}
}
// cerr << dp_u[v] << '\n';
// res = min(res, dp_u[t] + dp_v[t]);
}
cout << res << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
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... |