#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
vector<pii> g[100009];
vector<int> distS(100009, 1e18), distT(100009, 1e18), distU(100009, 1e18), distV(100009, 1e18);
priority_queue<pii,vector<pii>,greater<pii>> pq;
bool cp[100009];
void sp(vector<int>& dist, int u) {
pq.push({dist[u]=0, u});
while (!pq.empty()) {
auto [d,u]=pq.top(); pq.pop();
for (auto [v,w] : g[u]) {
if (cp[u] && cp[v])
w = 0;
if (d+w < dist[v])
pq.push({dist[v]=d+w, v});
}
}
}
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m, S, T, U, V;
cin >> n >> m >> S >> T >> U >> V;
while (m--) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
sp(distS, S), sp(distT, T);
for (int i = 1; i <= n; i++)
cp[i] = distS[i]+distT[i] == distS[T];
sp(distU, U);
cout << distU[V];
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... |