이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const long long INF = 1ll << 60;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n, m;
cin >> n >> m;
int S, T, U, V;
cin >> S >> T >> U >> V;
S--, T--, U--, V--;
vector<vector<pair<int, long long>>> g(n);
for (int i = 0; i < m; i++)
{
int u, v, w;
cin >> u >> v >> w;
u--, v--;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
auto dijkstra = [&](int s)
{
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.emplace(0, s);
vector<long long> dis(n, INF);
dis[s] = 0;
vector<bool> vis(n);
while (pq.size())
{
auto [d, u] = pq.top();
pq.pop();
if (vis[u])
continue;
vis[u] = 1;
for (auto &[v, w] : g[u])
{
if (dis[v] > dis[u] + w)
{
dis[v] = dis[u] + w;
pq.emplace(dis[v], v);
}
}
}
return dis;
};
auto disU = dijkstra(U), disV = dijkstra(V);
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.emplace(0, S);
vector<long long> dis(n, INF);
dis[S] = 0;
vector<bool> vis(n);
vector<vector<int>> stk(n);
vector<long long> ans(n, INF), minU(n, INF), minV(n, INF);
while (pq.size())
{
auto [d, u] = pq.top();
pq.pop();
if (vis[u])
continue;
vis[u] = 1;
minU[u] = disU[u], minV[u] = disV[u];
for (auto &v : stk[u])
{
ans[u] = min(ans[u], ans[v]);
minU[u] = min(minU[u], minU[v]);
minV[u] = min(minV[u], minV[v]);
}
ans[u] = min({ans[u], minU[u] + disV[u], minV[u] + disU[u]});
for (auto &[v, w] : g[u])
{
if (dis[v] > dis[u] + w)
{
stk[v].clear();
stk[v].push_back(u);
dis[v] = dis[u] + w;
pq.emplace(dis[v], v);
}
else if (dis[v] == dis[u] + w)
{
stk[v].push_back(u);
}
}
}
cout << min(ans[T], disU[V]) << '\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... |