이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n, m, s, t, u, v;
long long ans;
vector<pair<int, int>> a[N];
vector<int> g[N];
vector<long long> ds, dt, du, dv, dp1(N, 1e16), dp2(N, 1e16);
bool vs[N];
vector<long long> dijkstra(int s)
{
vector<long long> d(n+1, 1e16);
priority_queue<pair<long long, int>> q;
d[s] = 0;
q.push({0, s});
while (!q.empty())
{
long long dis = -q.top().first;
int u = q.top().second;
q.pop();
if (d[u] != dis) continue;
for (int i = 0; i < (int)a[u].size(); i++)
{
int v = a[u][i].first, w = a[u][i].second;
if (d[u]+w < d[v])
{
d[v] = d[u]+w;
q.push({-d[v], v});
}
}
}
return d;
}
pair<long long, long long> dfs(int u)
{
if (vs[u]) return {dp1[u], dp2[u]};
vs[u] = 1, dp1[u] = dv[u], dp2[u] = du[u];
for (int i = 0; i < (int)g[u].size(); i++)
{
int v = g[u][i];
pair<long long, long long> p = dfs(v);
dp1[u] = min(dp1[u], p.first);
dp2[u] = min(dp2[u], p.second);
}
ans = min(ans, min(du[u]+dp1[u], dv[u]+dp2[u]));
return {dp1[u], dp2[u]};
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> s >> t >> u >> v;
while (m--)
{
int u, v, c;
cin >> u >> v >> c;
a[u].push_back({v, c});
a[v].push_back({u, c});
}
ds = dijkstra(s);
dt = dijkstra(t);
du = dijkstra(u);
dv = dijkstra(v);
ans = du[v];
for (int u = 1; u <= n; u++)
for (int i = 0; i < (int)a[u].size(); i++)
if (ds[u]+a[u][i].second+dt[a[u][i].first] == ds[t])
g[u].push_back(a[u][i].first);
for (int i = 1; i <= n; i++)
if (!vs[i]) dfs(i);
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... |