This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100005;
const ll inf = 1e18;
int nodes, edges;
vector<pair<int, ll>> adj[MAXN];
void dijkstra(int source, vector<ll> &dist){
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
pq.push({0, source});
for (int i = 1; i <= nodes; i++) dist[i] = inf;
dist[source] = 0;
while (!pq.empty()){
ll d = pq.top().first; int x = pq.top().second; pq.pop();
if (dist[x] != d) continue;
for (auto nxt : adj[x]){
int nn = nxt.first; ll nd = nxt.second;
if (d + nd < dist[nn]){
dist[nn] = d + nd;
pq.push({dist[nn], nn});
}
}
}
}
ll dp(int x, vector<vector<int>> &spadj, vector<ll> &ddest, vector<ll> &memo){
if (memo[x] != -1) return memo[x];
ll ans = ddest[x];
for (int nxt : spadj[x]) ans = min(ans, dp(nxt, spadj, ddest, memo));
return memo[x] = ans;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int s, t, u, v; cin >> nodes >> edges >> s >> t >> u >> v;
vector<tuple<int, int, ll>> elist(edges);
for (int i = 0; i < edges; i++){
int a, b; ll d; cin >> a >> b >> d;
adj[a].push_back({b, d});
adj[b].push_back({a, d});
elist[i] = {a, b, d};
}
vector<ll> ds(nodes + 1), dt(nodes + 1), du(nodes + 1), dv(nodes + 1);
dijkstra(s, ds); dijkstra(t, dt); dijkstra(u, du); dijkstra(v, dv);
ll dst = ds[t];
vector<vector<int>> stot(nodes + 1), ttos(nodes + 1);
for (auto edge : elist){
int a, b; ll d; tie(a, b, d) = edge;
if (ds[a] + d + dt[b] == dst){
stot[a].push_back(b);
ttos[b].push_back(a);
}
else if (ds[b] + d + dt[a] == dst){
stot[b].push_back(a);
ttos[a].push_back(b);
}
}
vector<ll> memo1(nodes + 1, -1), memo2(nodes + 1, -1);
ll ans = du[v];
for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, stot, dv, memo1));
for (int i = 1; i <= nodes; i++) ans = min(ans, du[i] + dp(i, ttos, dv, memo2));
cout << ans;
}
# | 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... |