이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
vector<pair<int,ll>> g[100001];
bool vis[100001];
vector<int> dag[100001];
vector<ll> distS, distU, distV;
vector<ll> dijkstra(int src)
{
vector<ll> dist(N + 1, LLONG_MAX);
for (int u = 1; u <= N; u++)
vis[u] = false, dag[u] = vector<int>();
priority_queue<pair<ll, int>> pq;
dist[src] = 0;
pq.push({0LL, src});
while (!pq.empty())
{
int u = pq.top().second;
pq.pop();
if (vis[u]) continue;
vis[u] = true;
for (auto [v, l] : g[u])
if (dist[u] + l < dist[v])
{
dag[v] = {u};
dist[v] = dist[u] + l;
pq.push({-dist[v], v});
}
else if (dist[v] == dist[u] + l)
dag[v].push_back(u);
}
return dist;
}
ll dpU[100001], dpV[100001];
ll ans = LLONG_MAX;
void dfs(int x)
{
vis[x] = true;
dpU[x] = min(dpU[x], distU[x]);
dpV[x] = min(dpV[x], distV[x]);
for (int y : dag[x])
{
if (!vis[y])
dfs(y);
dpU[x] = min(dpU[x], dpU[y]);
dpV[x] = min(dpV[x], dpV[y]);
}
ans = min(ans, distU[x] + dpV[x]);
ans = min(ans, distV[x] + dpU[x]);
}
int main()
{
int M, S, T, U, V;
cin >> N >> M >> S >> T >> U >> V;
for (int i = 0, a, b; i < M; i++)
{
ll c;
cin >> a >> b >> c;
g[a].push_back({b, c});
g[b].push_back({a, c});
}
distU = dijkstra(U);
distV = dijkstra(V);
distS = dijkstra(S);
memset(vis, false, sizeof(vis));
for (int i = 1; i <= N; i++)
dpU[i] = dpV[i] = LLONG_MAX;
ans = distV[U];
dfs(T);
cout << ans << '\n';
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... |