#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int INF = 1e9;
const ll LINF = 1e18;
template<typename T>
bool minimize(T& a, const T& b) {
if (b < a) {a = b; return true;}
return false;
}
const int N = 1e5 + 5;
int n, m;
int s, t, a, b;
vector<ii> adj[N];
struct Node {
int u; ll d;
bool operator<(const Node& other) const {
return d > other.d;
}
};
ll dist_s[N];
ll dist_t[N];
ll dist_a[N];
ll dist_b[N];
void dijkstra(int s, ll dist[]) {
for (int u = 1; u <= n; u++) dist[u] = LINF;
priority_queue<Node> pq;
dist[s] = 0;
pq.push({s, dist[s]});
while (!pq.empty()) {
Node front = pq.top(); pq.pop();
int u = front.u; ll d = front.d;
if (d > dist[u]) continue;
for (ii v : adj[u]) {
if (minimize(dist[v.first], dist[u] + v.second)) {
pq.push({v.first, dist[v.first]});
}
}
}
}
vector<int> g[N];
ll memo[N];
ll dp_a(int u) {
ll& ans = memo[u];
if (ans != -1) return ans;
ans = dist_a[u];
for (int v : g[u]) {
minimize(ans, dp_a(v));
}
return ans;
}
ll dp_b(int u) {
ll& ans = memo[u];
if (ans != -1) return ans;
ans = dist_b[u];
for (int v : g[u]) {
minimize(ans, dp_b(v));
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
cin >> s >> t;
cin >> a >> b;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
dijkstra(s, dist_s);
dijkstra(t, dist_t);
for (int u = 1; u <= n; u++) {
for (ii v : adj[u]) {
if (dist_s[u] + v.second + dist_t[v.first] == dist_s[t]) {
g[u].push_back(v.first);
}
}
}
dijkstra(a, dist_a);
dijkstra(b, dist_b);
memset(memo, -1, sizeof memo);
ll ans = dist_a[b];
for (int u = 1; u <= n; u++) {
minimize(ans, dist_a[u] + dp_b(u));
}
memset(memo, -1, sizeof memo);
for (int u = 1; u <= n; u++) {
minimize(ans, dist_b[u] + dp_a(u));
}
cout << ans << '\n';
}
# | 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... |