library
This documentation is automatically generated by online-judge-tools/verification-helper
Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham
Undirected Shortest Path (remove one Edge)
(Graph/shortestpathremedge.hpp)
- View this file on GitHub
- Last update: 2025-01-28 06:32:12+09:00
- Include:
#include "Graph/shortestpathremedge.hpp"
Depends on
Lowest Common Ancestor
(Graph/lca.hpp)
Code
#pragma once
#include "Graph/lca.hpp"
template <typename T>
vector<T> UndirectedShortestPathRemoveEdge(int n,
vector<tuple<int, int, T>> &es,
int s, int t) {
using P = pair<T, int>;
vector g(n, vector<tuple<int, T, int>>());
rep(i, 0, SZ(es)) {
auto [u, v, w] = es[i];
assert(w > 0);
g[u].push_back({v, w, i});
g[v].push_back({u, w, i});
}
auto dijk = [&](int st, vector<int> &etrace,
vector<int> &vtrace) -> pair<vector<T>, vector<int>> {
vector<T> dist(n, INF);
vector<int> pre(n, -1); // id
priority_queue<P, vector<P>, greater<P>> pq;
dist[st] = 0;
pq.push({0, st});
if (SZ(etrace)) {
int cur = st;
T cost = 0;
rep(i, 0, SZ(etrace)) {
cur = vtrace[i + 1];
pre[cur] = etrace[i];
cost += get<2>(es[etrace[i]]);
dist[cur] = cost;
pq.push({cost, cur});
}
}
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (dist[v] != d)
continue;
for (auto &[to, cost, id] : g[v])
if (chmin(dist[to], dist[v] + cost)) {
pq.push({dist[to], to});
pre[to] = id;
}
}
return {dist, pre};
};
vector<int> etrace, vtrace;
auto [ds, ps] = dijk(s, etrace, vtrace);
vector<int> ord(n, -1);
{
int cur = t;
vtrace.push_back(t);
for (;;) {
if (cur == s)
break;
int id = ps[cur];
etrace.push_back(id);
cur = (get<0>(es[id]) == cur ? get<1>(es[id]) : get<0>(es[id]));
vtrace.push_back(cur);
}
}
auto [dt, pt] = dijk(t, etrace, vtrace);
reverse(ALL(etrace));
reverse(ALL(vtrace));
rep(i, 0, SZ(vtrace)) ord[vtrace[i]] = i;
vector<T> ret(SZ(es), ds[t]);
for (auto &id : etrace)
ret[id] = INF;
LCA lca1(n), lca2(n);
rep(v, 0, n) if (ps[v] != -1) {
auto [x, y, _] = es[ps[v]];
int u = (x == v ? y : x);
lca1.add_edge(v, u);
}
rep(v, 0, n) if (pt[v] != -1) {
auto [x, y, _] = es[pt[v]];
int u = (x == v ? y : x);
lca2.add_edge(v, u);
}
lca1.run(s);
lca2.run(t);
vector add(n, vector<pair<T, ll>>());
vector rem(n, vector<pair<T, ll>>());
for (auto &[u, v, w] : es) {
if (ds[u] + w + dt[v] == ds[t] or ds[v] + w + dt[u] == ds[t])
continue;
rep(_, 0, 2) {
int x = lca1.lca(t, u);
int y = lca2.lca(s, v);
if (x != y) {
if (ord[x] > ord[y])
swap(x, y);
add[x].push_back({ds[u] + dt[v] + w, u * n + v});
rem[y].push_back({ds[u] + dt[v] + w, u * n + v});
}
swap(u, v);
}
}
set<P> st;
rep(i, 0, SZ(etrace)) {
for (auto &[cand, id] : add[vtrace[i]]) {
st.insert({cand, id});
}
for (auto &[cand, id] : rem[vtrace[i]]) {
st.erase({cand, id});
}
if (SZ(st)) {
chmin(ret[etrace[i]], (*st.begin()).first);
}
}
return ret;
}
/**
* @brief Undirected Shortest Path (remove one Edge)
*/#line 2 "Graph/lca.hpp"
struct LCA{
LCA(int _n=0):n(_n),g(_n),depth(_n+1,inf),start(_n){}
void add_edge(int u,int v){
g[u].push_back(v);
g[v].push_back(u);
}
void run(int root=0){
depth[root]=0;
dfs(root,-1);
N=1;
while(N<int(euler.size()))N<<=1;
tree.resize(N*2,n);
rep(i,0,euler.size())tree[N+i]=euler[i];
for(int i=N-1;i>0;i--)tree[i]=op(tree[i*2],tree[i*2+1]);
}
int lca(int u,int v){
int a=start[u],b=start[v];
if(a>b)swap(a,b);
b++;
int res=n;
for(int T=b-a;T>=1;T=b-a){
int x=a|((1U<<31)>>__builtin_clz(T));
int y=x&-x,k=__builtin_ctz(x);
res=op(res,tree[(N|a)>>k]);
a+=y;
}
return res;
}
private:
int n,N;
vector<vector<int>> g;
vector<int> depth,start,euler,tree;
void dfs(int v,int p){
start[v]=euler.size();
euler.push_back(v);
for(auto& to:g[v])if(to!=p){
depth[to]=depth[v]+1;
dfs(to,v);
euler.push_back(v);
}
}
int op(int u,int v){
if(depth[u]<depth[v])return u;
else return v;
}
};
/**
* @brief Lowest Common Ancestor
*/
#line 3 "Graph/shortestpathremedge.hpp"
template <typename T>
vector<T> UndirectedShortestPathRemoveEdge(int n,
vector<tuple<int, int, T>> &es,
int s, int t) {
using P = pair<T, int>;
vector g(n, vector<tuple<int, T, int>>());
rep(i, 0, SZ(es)) {
auto [u, v, w] = es[i];
assert(w > 0);
g[u].push_back({v, w, i});
g[v].push_back({u, w, i});
}
auto dijk = [&](int st, vector<int> &etrace,
vector<int> &vtrace) -> pair<vector<T>, vector<int>> {
vector<T> dist(n, INF);
vector<int> pre(n, -1); // id
priority_queue<P, vector<P>, greater<P>> pq;
dist[st] = 0;
pq.push({0, st});
if (SZ(etrace)) {
int cur = st;
T cost = 0;
rep(i, 0, SZ(etrace)) {
cur = vtrace[i + 1];
pre[cur] = etrace[i];
cost += get<2>(es[etrace[i]]);
dist[cur] = cost;
pq.push({cost, cur});
}
}
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (dist[v] != d)
continue;
for (auto &[to, cost, id] : g[v])
if (chmin(dist[to], dist[v] + cost)) {
pq.push({dist[to], to});
pre[to] = id;
}
}
return {dist, pre};
};
vector<int> etrace, vtrace;
auto [ds, ps] = dijk(s, etrace, vtrace);
vector<int> ord(n, -1);
{
int cur = t;
vtrace.push_back(t);
for (;;) {
if (cur == s)
break;
int id = ps[cur];
etrace.push_back(id);
cur = (get<0>(es[id]) == cur ? get<1>(es[id]) : get<0>(es[id]));
vtrace.push_back(cur);
}
}
auto [dt, pt] = dijk(t, etrace, vtrace);
reverse(ALL(etrace));
reverse(ALL(vtrace));
rep(i, 0, SZ(vtrace)) ord[vtrace[i]] = i;
vector<T> ret(SZ(es), ds[t]);
for (auto &id : etrace)
ret[id] = INF;
LCA lca1(n), lca2(n);
rep(v, 0, n) if (ps[v] != -1) {
auto [x, y, _] = es[ps[v]];
int u = (x == v ? y : x);
lca1.add_edge(v, u);
}
rep(v, 0, n) if (pt[v] != -1) {
auto [x, y, _] = es[pt[v]];
int u = (x == v ? y : x);
lca2.add_edge(v, u);
}
lca1.run(s);
lca2.run(t);
vector add(n, vector<pair<T, ll>>());
vector rem(n, vector<pair<T, ll>>());
for (auto &[u, v, w] : es) {
if (ds[u] + w + dt[v] == ds[t] or ds[v] + w + dt[u] == ds[t])
continue;
rep(_, 0, 2) {
int x = lca1.lca(t, u);
int y = lca2.lca(s, v);
if (x != y) {
if (ord[x] > ord[y])
swap(x, y);
add[x].push_back({ds[u] + dt[v] + w, u * n + v});
rem[y].push_back({ds[u] + dt[v] + w, u * n + v});
}
swap(u, v);
}
}
set<P> st;
rep(i, 0, SZ(etrace)) {
for (auto &[cand, id] : add[vtrace[i]]) {
st.insert({cand, id});
}
for (auto &[cand, id] : rem[vtrace[i]]) {
st.erase({cand, id});
}
if (SZ(st)) {
chmin(ret[etrace[i]], (*st.begin()).first);
}
}
return ret;
}
/**
* @brief Undirected Shortest Path (remove one Edge)
*/