35pts TLE 求助
- 板块P6777 [NOI2020] 翻修道路
- 楼主YUYGFGG
- 当前回复1
- 已保存回复1
- 发布时间2025/8/30 23:11
- 上次更新2025/8/31 16:56:08
查看原帖
被骇客银狼阻止的越权访问保存失败
35pts TLE 求助
大样例本机O2要跑4.5s左右，可能是被卡常了？
用的是论文里的算法，应该没什么问题吧（心虚）
代码有点长，要提交的话先用这个网站压缩一下才行
#include <algorithm>
#include <array>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <limits>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
constexpr int64_t INF = numeric_limits<int64_t>::max() / 3;
constexpr int32_t INF_INT = numeric_limits<int32_t>::max();
typedef int32_t Vertex;
typedef vector<Vertex> Path;
constexpr Vertex V_NONE = 0;
typedef uint64_t PackedKey;
struct optimized_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
template <typename T> size_t operator()(T x) const {
static const uint64_t FIXED_RANDOM =
chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(static_cast<uint64_t>(x) + FIXED_RANDOM);
}
};
inline PackedKey edge_key(Vertex u, Vertex v) {
if (u > v)
swap(u, v);
return ((uint64_t)v << 32) | (uint32_t)u;
}
inline PackedKey directed_edge_key(Vertex u, Vertex v) {
return ((uint64_t)u << 32) | (uint32_t)v;
}
inline PackedKey lr_key(int32_t r_id, Vertex u) {
return ((uint64_t)r_id << 32) | (uint32_t)u;
}
inline pair<Vertex, Vertex> unpack_edge_key(PackedKey key) {
return {(Vertex)(key & 0xFFFFFFFF), (Vertex)(key >> 32)};
}
template <typename V>
using OptimizedMap = unordered_map<PackedKey, V, optimized_hash>;
template <typename K> using OptimizedSet = unordered_set<K, optimized_hash>;
struct Edge {
Vertex to;
int64_t weight;
int32_t id;
};
struct OriginalEdge {
Vertex u, v;
int64_t weight;
int32_t id;
OriginalEdge(Vertex u, Vertex v, int64_t w, int32_t id)
: u(u), v(v), weight(w), id(id) {}
};
class Graph {
public:
vector<vector<Edge>> adj;
int32_t N;
vector<OriginalEdge> edge_storage;
vector<const OriginalEdge*> edge_list;
vector<const OriginalEdge*> edge_id_to_ptr;
int32_t max_edge_id = -1;
Graph() : N(0) {}
Graph(int32_t vertex_count, int32_t edge_count) {
N = vertex_count + 1;
adj.resize(N);
if (edge_count > 0) {
edge_storage.reserve(edge_count);
edge_list.reserve(edge_count);
edge_id_to_ptr.reserve(edge_count + 1);
}
}
void ensure_vertex_capacity(Vertex u) {
if (u >= N) {
N = u + 1;
adj.resize(N);
}
}
void ensure_id_capacity(int32_t id) {
if (id != -1 && id >= static_cast<int32_t>(edge_id_to_ptr.size())) {
edge_id_to_ptr.resize(id + 1, nullptr);
}
}
void add_directed_edge(Vertex u, Vertex v, int64_t w, int32_t id) {
adj[u].push_back({v, w, id});
}
void add_edge(Vertex u, Vertex v, int64_t w, int32_t id,
const OriginalEdge* existing_ptr = nullptr) {
if (id != -1) {
max_edge_id = max(max_edge_id, id);
ensure_id_capacity(id);
if (edge_id_to_ptr[id]) {
return;
}
}
ensure_vertex_capacity(u);
ensure_vertex_capacity(v);
add_directed_edge(u, v, w, id);
add_directed_edge(v, u, w, id);
if (id != -1) {
const OriginalEdge* ptr;
if (existing_ptr) {
ptr = existing_ptr;
} else {
edge_storage.emplace_back(u, v, w, id);
ptr = &edge_storage.back();
}
edge_list.push_back(ptr);
edge_id_to_ptr[id] = ptr;
}
}
bool are_adjacent(Vertex u, Vertex v) const {
if (u >= N || v >= N || u == 0 || v == 0)
return false;
const vector<Edge>* adj_list = &adj[u];
Vertex target = v;
if (adj[u].size() > adj[v].size()) {
adj_list = &adj[v];
target = u;
}
for (const auto& edge : *adj_list) {
if (edge.to == target)
return true;
}
return false;
}
const OriginalEdge* get_edge_ptr(int32_t id) const {
if (id < 0 || id >= static_cast<int32_t>(edge_id_to_ptr.size()))
return nullptr;
return edge_id_to_ptr[id];
}
};
class MultiGraph {
public:
vector<vector<pair<Vertex, int32_t>>> adj;
int32_t N;
MultiGraph(int32_t size) : N(size) { adj.resize(N); }
};
int64_t get_edge_length(const Graph& G, Vertex u, Vertex v) {
if (u >= G.N || v >= G.N || u == 0 || v == 0)
return INF;
const vector<Edge>* adj_list = &G.adj[u];
Vertex target = v;
if (G.adj[u].size() > G.adj[v].size()) {
adj_list = &G.adj[v];
target = u;
}
for (const auto& edge : *adj_list) {
if (edge.to == target) {
return edge.weight;
}
}
return INF;
}
vector<int32_t> get_P_indices_vec(const Path& P, int32_t N) {
vector<int32_t> indices(N, -1);
for (int32_t i = 0; i < static_cast<int32_t>(P.size()); ++i) {
if (P[i] > 0 && P[i] < N) {
indices[P[i]] = i;
}
}
return indices;
}
bool is_useful_weighted(const Path& r, const vector<int64_t>& weights,
const Graph& G) {
if (r.size() < 3)
return false;
for (int32_t i = 0; i <= static_cast<int32_t>(r.size()) - 3; ++i) {
int64_t len_path = weights[i] + weights[i + 1];
int64_t len_edge = get_edge_length(G, r[i], r[i + 2]);
if (len_edge != INF && len_path >= len_edge) {
return false;
}
}
return true;
}
pair<int64_t, Path> dijkstra(const Graph& G, Vertex S, Vertex T,
const vector<uint8_t>& is_forbidden_v = {},
const vector<uint8_t>& is_forbidden_e = {}) {
if (S <= 0 || S >= G.N || T <= 0 || T >= G.N)
return {INF, {}};
if (!is_forbidden_v.empty()) {
if ((S < static_cast<int32_t>(is_forbidden_v.size()) &&
is_forbidden_v[S]) ||
(T < static_cast<int32_t>(is_forbidden_v.size()) &&
is_forbidden_v[T]))
return {INF, {}};
}
vector<int64_t> dist(G.N, INF);
vector<Vertex> parent(G.N, V_NONE);
using PQElement = pair<int64_t, Vertex>;
priority_queue<PQElement, vector<PQElement>, greater<PQElement>> pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()) {
int64_t d = pq.top().first;
Vertex u = pq.top().second;
pq.pop();
if (d > dist[u])
continue;
if (u == T)
break;
for (const auto& edge : G.adj[u]) {
Vertex v = edge.to;
if (!is_forbidden_v.empty() &&
v < static_cast<int32_t>(is_forbidden_v.size()) &&
is_forbidden_v[v])
continue;
if (edge.id != -1 && !is_forbidden_e.empty() &&
edge.id < static_cast<int32_t>(is_forbidden_e.size()) &&
is_forbidden_e[edge.id])
continue;
int64_t new_dist = dist[u] + edge.weight;
if (new_dist < dist[v]) {
dist[v] = new_dist;
parent[v] = u;
pq.push({dist[v], v});
}
}
}
if (dist[T] == INF) {
return {INF, {}};
}
Path path;
path.reserve(G.N);
Vertex curr = T;
while (curr != S) {
path.push_back(curr);
if (parent[curr] == V_NONE)
return {INF, {}};
curr = parent[curr];
}
path.push_back(S);
reverse(path.begin(), path.end());
return {dist[T], path};
}
class BridgeFinder {
public:
const Graph& G;
vector<int32_t> tin, low;
int timer;
vector<uint8_t> is_bridge;
int max_id = -1;
BridgeFinder(const Graph& G) : G(G) {}
struct DFSState {
Vertex v;
Vertex p;
int edge_id_in;
size_t neighbor_index;
};
void find_Bridges() {
timer = 0;
tin.assign(G.N, -1);
low.assign(G.N, -1);
vector<int32_t> bridge_ids_vec;
bridge_ids_vec.reserve(G.edge_list.size());
vector<DFSState> stack;
if (G.N > 1)
stack.reserve(G.N);
for (Vertex start_node = 1; start_node < G.N; ++start_node) {
if (tin[start_node] != -1)
continue;
stack.push_back({start_node, V_NONE, -1, 0});
while (!stack.empty()) {
DFSState& state = stack.back();
if (state.neighbor_index == 0) {
if (tin[state.v] == -1) {
tin[state.v] = low[state.v] = timer++;
}
}
const auto& adj_v = G.adj[state.v];
bool pushed_child = false;
while (state.neighbor_index < adj_v.size()) {
const auto& edge = adj_v[state.neighbor_index];
Vertex to = edge.to;
state.neighbor_index++;
if (to == state.p)
continue;
if (tin[to] != -1) {
low[state.v] = min(low[state.v], tin[to]);
} else {
stack.push_back({to, state.v, edge.id, 0});
pushed_child = true;
break;
}
}
if (pushed_child) {
continue;
}
Vertex v = state.v;
Vertex p = state.p;
int32_t edge_id_in = state.edge_id_in;
stack.pop_back();
if (p != V_NONE) {
low[p] = min(low[p], low[v]);
if (low[v] > tin[p]) {
if (edge_id_in != -1) {
bridge_ids_vec.push_back(edge_id_in);
max_id = max(max_id, edge_id_in);
}
}
}
}
}
if (max_id != -1) {
is_bridge.assign(max_id + 1, false);
for (int32_t id : bridge_ids_vec) {
is_bridge[id] = true;
}
}
}
};
class BCCFinder {
public:
const Graph& G;
const OptimizedSet<PackedKey>* forbidden_edges_set = nullptr;
vector<int32_t> tin, low;
int32_t timer;
vector<OptimizedSet<Vertex>> BCCs;
vector<uint8_t> is_ap;
vector<PackedKey> edge_stack;
OptimizedMap<int32_t> edge_to_BCC;
BCCFinder(const Graph& G,
const OptimizedSet<PackedKey>* forbidden = nullptr)
: G(G), forbidden_edges_set(forbidden) {}
struct DFSState {
Vertex v;
Vertex p;
size_t neighbor_index;
int32_t children_count;
};
void find_BCCs() {
timer = 0;
tin.assign(G.N, -1);
low.assign(G.N, -1);
BCCs.clear();
is_ap.assign(G.N, false);
edge_stack.clear();
edge_stack.reserve(G.edge_list.size());
edge_to_BCC.clear();
edge_to_BCC.reserve(G.edge_list.size());
vector<DFSState> stack;
if (G.N > 1)
stack.reserve(G.N);
for (Vertex start_node = 1; start_node < G.N; ++start_node) {
if (tin[start_node] != -1)
continue;
stack.push_back({start_node, V_NONE, 0, 0});
while (!stack.empty()) {
DFSState& state = stack.back();
if (state.neighbor_index == 0) {
if (tin[state.v] == -1) {
tin[state.v] = low[state.v] = timer++;
}
}
const auto& adj_v = G.adj[state.v];
bool pushed_child = false;
while (state.neighbor_index < adj_v.size()) {
const auto& edge = adj_v[state.neighbor_index];
Vertex to = edge.to;
state.neighbor_index++;
if (to == state.p)
continue;
PackedKey current_edge_key = edge_key(state.v, to);
if (forbidden_edges_set &&
forbidden_edges_set->count(current_edge_key)) {
continue;
}
if (tin[to] != -1) {
low[state.v] = min(low[state.v], tin[to]);
if (tin[to] < tin[state.v]) {
edge_stack.push_back(current_edge_key);
}
} else {
edge_stack.push_back(current_edge_key);
stack.push_back({to, state.v, 0, 0});
pushed_child = true;
break;
}
}
if (pushed_child) {
continue;
}
Vertex v = state.v;
Vertex p = state.p;
int32_t children_count = state.children_count;
stack.pop_back();
if (p != V_NONE) {
DFSState& parent_state = stack.back();
parent_state.children_count++;
low[p] = min(low[p], low[v]);
if (low[v] >= tin[p]) {
if (parent_state.p != V_NONE) {
is_ap[p] = true;
}
int32_t bcc_index = BCCs.size();
OptimizedSet<Vertex> component;
PackedKey critical_edge_key = edge_key(p, v);
while (!edge_stack.empty()) {
PackedKey e_key = edge_stack.back();
edge_stack.pop_back();
pair<Vertex, Vertex> e = unpack_edge_key(e_key);
if (e.first < G.N) {
component.insert(e.first);
}
if (e.second < G.N) {
component.insert(e.second);
}
edge_to_BCC[e_key] = bcc_index;
if (e_key == critical_edge_key)
break;
}
if (!component.empty()) {
BCCs.push_back(std::move(component));
}
}
} else {
if (children_count > 1) {
is_ap[v] = true;
}
}
}
}
}
};
class BCCFinder_Multi {
public:
const MultiGraph& MG;
vector<int32_t> tin, low;
int32_t timer;
vector<vector<int32_t>> BCC_edges;
vector<int32_t> edge_stack;
BCCFinder_Multi(const MultiGraph& MG) : MG(MG) {}
struct DFSState {
Vertex v;
Vertex p;
int32_t parent_edge_id;
size_t neighbor_index;
};
void find_BCCs() {
timer = 0;
tin.assign(MG.N, -1);
low.assign(MG.N, -1);
BCC_edges.clear();
edge_stack.clear();
vector<DFSState> stack;
if (MG.N > 1)
stack.reserve(MG.N);
for (Vertex start_node = 1; start_node < MG.N; ++start_node) {
if (tin[start_node] != -1)
continue;
if (MG.adj[start_node].empty())
continue;
stack.push_back({start_node, V_NONE, -1, 0});
while (!stack.empty()) {
DFSState& state = stack.back();
if (state.neighbor_index == 0) {
if (tin[state.v] == -1) {
tin[state.v] = low[state.v] = timer++;
}
}
const auto& adj_v = MG.adj[state.v];
bool pushed_child = false;
while (state.neighbor_index < adj_v.size()) {
const auto& edge_info = adj_v[state.neighbor_index];
Vertex to = edge_info.first;
int32_t current_edge_id = edge_info.second;
state.neighbor_index++;
if (current_edge_id == state.parent_edge_id)
continue;
if (tin[to] != -1) {
low[state.v] = min(low[state.v], tin[to]);
if (tin[to] < tin[state.v]) {
edge_stack.push_back(current_edge_id);
}
} else {
edge_stack.push_back(current_edge_id);
stack.push_back({to, state.v, current_edge_id, 0});
pushed_child = true;
break;
}
}
if (pushed_child)
continue;
Vertex v = state.v;
Vertex p = state.p;
int32_t parent_edge_id = state.parent_edge_id;
stack.pop_back();
if (p != V_NONE) {
low[p] = min(low[p], low[v]);
if (low[v] >= tin[p]) {
vector<int32_t> component;
while (!edge_stack.empty()) {
int32_t e_id = edge_stack.back();
edge_stack.pop_back();
component.push_back(e_id);
if (e_id == parent_edge_id)
break;
}
if (!component.empty()) {
BCC_edges.push_back(std::move(component));
}
}
}
}
}
}
};
struct BCTree {
int32_t N;
vector<vector<int32_t>> adj;
int32_t get_ap_id(Vertex v) const { return v; }
int32_t get_bcc_id(int32_t i) const { return N + i; }
void build(const BCCFinder& bcc_finder, int32_t graph_N) {
N = graph_N;
const auto& BCCs = bcc_finder.BCCs;
const auto& is_ap = bcc_finder.is_ap;
int32_t total_nodes = N + BCCs.size();
adj.clear();
adj.resize(total_nodes);
for (int32_t i = 0; i < static_cast<int32_t>(BCCs.size()); ++i) {
int32_t bcc_id = get_bcc_id(i);
for (Vertex v : BCCs[i]) {
if (v < static_cast<int32_t>(is_ap.size()) && is_ap[v]) {
int32_t ap_id = get_ap_id(v);
adj[bcc_id].push_back(ap_id);
adj[ap_id].push_back(bcc_id);
}
}
}
}
vector<int32_t> find_path(int32_t start_node, int32_t end_node) {
if (start_node == -1 || end_node == -1)
return {};
if (start_node == end_node)
return {start_node};
int32_t total_nodes = adj.size();
if (start_node >= total_nodes || end_node >= total_nodes ||
start_node <= 0 || end_node <= 0)
return {};
queue<int32_t> q;
vector<int32_t> parent(total_nodes, -1);
q.push(start_node);
parent[start_node] = 0;
bool found = false;
while (!q.empty()) {
int32_t u = q.front();
q.pop();
if (u == end_node) {
found = true;
break;
}
for (const int v : adj[u]) {
if (parent[v] == -1) {
parent[v] = u;
q.push(v);
}
}
}
if (!found)
return {};
vector<int32_t> path;
int32_t curr = end_node;
while (curr != 0) {
path.push_back(curr);
curr = parent[curr];
}
reverse(path.begin(), path.end());
return path;
}
};
vector<uint8_t> compute_BAD_G(const Graph& G, Vertex S, Vertex T) {
BCCFinder bcc_finder(G);
bcc_finder.find_BCCs();
BCTree bct;
bct.build(bcc_finder, G.N);
const auto& is_ap = bcc_finder.is_ap;
const auto& BCCs = bcc_finder.BCCs;
vector<int32_t> vertex_to_bcc(G.N, -1);
for (int32_t i = 0; i < static_cast<int32_t>(BCCs.size()); ++i) {
for (Vertex v : BCCs[i]) {
if (v < G.N &&
(v >= static_cast<int32_t>(is_ap.size()) || !is_ap[v])) {
vertex_to_bcc[v] = i;
}
}
}
auto find_tau = [&](Vertex V) {
if (V <= 0 || V >= G.N)
return -1;
if (V < static_cast<int32_t>(is_ap.size()) && is_ap[V]) {
return bct.get_ap_id(V);
} else {
int32_t bcc_index = vertex_to_bcc[V];
if (bcc_index != -1)
return bct.get_bcc_id(bcc_index);
}
return -1;
};
int32_t S_tau = find_tau(S);
int32_t T_tau = find_tau(T);
vector<int32_t> path = bct.find_path(S_tau, T_tau);
vector<uint8_t> is_bad(G.N, false);
vector<int32_t> degrees_in_C_dat(G.N, 0);
vector<uint8_t> in_C_ws(G.N, false);
for (int32_t index = 0; index < static_cast<int32_t>(path.size());
++index) {
const int32_t node_id = path[index];
if (node_id >= G.N) {
int32_t bcc_index = node_id - G.N;
if (bcc_index < 0 || bcc_index >= static_cast<int32_t>(BCCs.size()))
continue;
const auto& C = BCCs[bcc_index];
for (Vertex v : C) {
if (v < G.N)
in_C_ws[v] = true;
}
for (Vertex u : C) {
int32_t degree = 0;
if (u < G.N) {
for (const auto& edge : G.adj[u]) {
if (edge.to < G.N && in_C_ws[edge.to])
degree++;
}
degrees_in_C_dat[u] = degree;
}
}
for (Vertex u : C) {
if (u == S || u == T || u >= G.N)
continue;
if (degrees_in_C_dat[u] == 2) {
bool u_is_AP_connector = false;
int32_t u_ap_id = bct.get_ap_id(u);
if (index > 0 && path[index - 1] == u_ap_id) {
u_is_AP_connector = true;
}
if (!u_is_AP_connector &&
index < static_cast<int32_t>(path.size()) - 1 &&
path[index + 1] == u_ap_id) {
u_is_AP_connector = true;
}
if (!u_is_AP_connector) {
is_bad[u] = true;
}
}
}
for (Vertex v : C) {
if (v < G.N)
in_C_ws[v] = false;
}
}
}
return is_bad;
}
Path validate_separator(const vector<const OriginalEdge*>& R, const Graph& G,
bool required_odd_P_index,
const vector<int32_t>& P_indices,
const vector<int32_t>& min_P_neighbor_index,
vector<vector<pair<Vertex, int64_t>>>& adj_R_ws,
vector<uint8_t>& in_R_ws) {
if (R.empty())
return {};
const int32_t N = G.N;
vector<Vertex> vertices_R;
vertices_R.reserve(R.size() + 1);
for (const auto* edge_ptr : R) {
Vertex u = edge_ptr->u;
Vertex v = edge_ptr->v;
int64_t w = edge_ptr->weight;
if (u >= N || v >= N || u == 0 || v == 0)
continue;
adj_R_ws[u].push_back({v, w});
adj_R_ws[v].push_back({u, w});
if (!in_R_ws[u]) {
in_R_ws[u] = true;
vertices_R.push_back(u);
}
if (!in_R_ws[v]) {
in_R_ws[v] = true;
vertices_R.push_back(v);
}
}
auto cleanup = [&]() {
for (Vertex v : vertices_R) {
in_R_ws[v] = false;
adj_R_ws[v].clear();
}
};
vector<Vertex> endpoints;
for (Vertex v : vertices_R) {
const auto& neighbors = adj_R_ws[v];
if (neighbors.size() > 2) {
cleanup();
return {};
}
if (neighbors.size() == 1)
endpoints.push_back(v);
}
if (endpoints.size() != 2) {
cleanup();
return {};
}
Path r;
vector<int64_t> r_weights;
r.reserve(R.size() + 1);
r_weights.reserve(R.size());
Vertex curr = endpoints[0];
Vertex prev = V_NONE;
while (curr != V_NONE) {
r.push_back(curr);
Vertex next = V_NONE;
const auto& neighbors = adj_R_ws[curr];
for (const auto& edge_info : neighbors) {
Vertex neighbor = edge_info.first;
int64_t weight = edge_info.second;
if (neighbor != prev) {
next = neighbor;
r_weights.push_back(weight);
break;
}
}
prev = curr;
curr = next;
}
cleanup();
if (r.size() != R.size() + 1)
return {};
auto check_alignment = [&](const Path& path) {
int32_t last_P_idx = -1;
for (Vertex v : path) {
if (v < static_cast<int32_t>(P_indices.size()) &&
P_indices[v] != -1) {
if (P_indices[v] <= last_P_idx)
return false;
last_P_idx = P_indices[v];
}
}
return true;
};
if (!check_alignment(r)) {
reverse(r.begin(), r.end());
reverse(r_weights.begin(), r_weights.end());
if (!check_alignment(r))
return {};
}
if (r.size() < 4)
return {};
for (size_t i = 2; i < r.size(); ++i) {
if (r[i] >= static_cast<int32_t>(P_indices.size()) ||
P_indices[r[i]] == -1)
return {};
}
int32_t idx_r2 = P_indices[r[2]];
if ((idx_r2 % 2 != 0) != required_odd_P_index)
return {};
if (!is_useful_weighted(r, r_weights, G))
return {};
Vertex r0 = r[0];
bool traversable = false;
if (r0 < static_cast<int32_t>(P_indices.size()) && P_indices[r0] != -1) {
if (P_indices[r0] < idx_r2)
traversable = true;
}
if (!traversable) {
if (r0 < static_cast<int32_t>(min_P_neighbor_index.size()) &&
min_P_neighbor_index[r0] != INF_INT) {
if (min_P_neighbor_index[r0] < idx_r2)
traversable = true;
}
}
if (!traversable)
return {};
return r;
}
void compute_S_Separators(const Graph& G, const Path& P, bool find_odd_S_sep,
vector<Path>& X_result) {
if (P.empty())
return;
bool merge_even_P_indices = find_odd_S_sep;
vector<int32_t> P_indices = get_P_indices_vec(P, G.N);
vector<int32_t> min_P_neighbor_index(G.N, INF_INT);
for (int32_t i = 0; i < static_cast<int32_t>(P.size()); ++i) {
Vertex u = P[i];
if (u >= G.N || u == 0)
continue;
if (i < min_P_neighbor_index[u])
min_P_neighbor_index[u] = i;
for (const auto& edge : G.adj[u]) {
Vertex v = edge.to;
if (v >= G.N || v == 0)
continue;
if (i < min_P_neighbor_index[v])
min_P_neighbor_index[v] = i;
}
}
vector<vector<Vertex>> MergeGraphAdj(G.N);
for (int32_t i = 0; i <= static_cast<int32_t>(P.size()) - 3; ++i) {
bool parity_match = merge_even_P_indices ? (i % 2 == 0) : (i % 2 != 0);
if (parity_match) {
if (G.are_adjacent(P[i], P[i + 2])) {
MergeGraphAdj[P[i]].push_back(P[i + 2]);
MergeGraphAdj[P[i + 2]].push_back(P[i]);
}
}
}
for (Vertex u = 1; u < G.N; ++u) {
if (P_indices[u] != -1)
continue;
if (min_P_neighbor_index[u] == INF_INT)
continue;
int min_index = min_P_neighbor_index[u];
for (const auto& edge : G.adj[u]) {
Vertex v = edge.to;
if (v >= G.N || v == 0)
continue;
if (P_indices[v] != -1) {
int idx_v = P_indices[v];
bool parity_match =
merge_even_P_indices ? (idx_v % 2 == 0) : (idx_v % 2 != 0);
if (parity_match && idx_v > min_index) {
MergeGraphAdj[u].push_back(v);
MergeGraphAdj[v].push_back(u);
}
}
}
}
vector<Vertex> vertex_to_fat(G.N, V_NONE);
queue<Vertex> q;
for (Vertex v = 1; v < G.N; ++v) {
if (vertex_to_fat[v] != V_NONE)
continue;
Vertex fat_id = v;
q.push(v);
vertex_to_fat[v] = fat_id;
while (!q.empty()) {
Vertex u = q.front();
q.pop();
for (Vertex neighbor : MergeGraphAdj[u]) {
if (vertex_to_fat[neighbor] == V_NONE) {
vertex_to_fat[neighbor] = fat_id;
q.push(neighbor);
}
}
}
}
MultiGraph GMERGE(G.N);
for (const auto* edge_ptr : G.edge_list) {
Vertex u = edge_ptr->u;
Vertex v = edge_ptr->v;
Vertex fat_u = (u < G.N) ? vertex_to_fat[u] : V_NONE;
Vertex fat_v = (v < G.N) ? vertex_to_fat[v] : V_NONE;
if (fat_u != V_NONE && fat_v != V_NONE && fat_u != fat_v) {
int edge_id = edge_ptr->id;
GMERGE.adj[fat_u].push_back({fat_v, edge_id});
GMERGE.adj[fat_v].push_back({fat_u, edge_id});
}
}
BCCFinder_Multi bcc_finder(GMERGE);
bcc_finder.find_BCCs();
vector<Vertex> C_vertices_vec;
vector<uint8_t> in_C_vertices_ws(G.N, false);
vector<vector<pair<Vertex, int64_t>>> adj_R_reusable(G.N);
vector<uint8_t> in_R_reusable(G.N, false);
int32_t max_id = G.max_edge_id;
vector<uint8_t> in_C_edges_ws;
if (max_id != -1) {
in_C_edges_ws.resize(max_id + 1, false);
}
for (const auto& C_edges : bcc_finder.BCC_edges) {
C_vertices_vec.clear();
for (int32_t edge_id : C_edges) {
if (edge_id >= 0 && edge_id <= max_id)
in_C_edges_ws[edge_id] = true;
}
for (int32_t edge_id : C_edges) {
const OriginalEdge* edge_ptr = G.get_edge_ptr(edge_id);
if (!edge_ptr)
continue;
Vertex fat_u =
(edge_ptr->u < G.N) ? vertex_to_fat[edge_ptr->u] : V_NONE;
Vertex fat_v =
(edge_ptr->v < G.N) ? vertex_to_fat[edge_ptr->v] : V_NONE;
if (fat_u != V_NONE && !in_C_vertices_ws[fat_u]) {
in_C_vertices_ws[fat_u] = true;
C_vertices_vec.push_back(fat_u);
}
if (fat_v != V_NONE && !in_C_vertices_ws[fat_v]) {
in_C_vertices_ws[fat_v] = true;
C_vertices_vec.push_back(fat_v);
}
}
for (Vertex u : C_vertices_vec) {
vector<const OriginalEdge*> R;
if (u < GMERGE.N) {
R.reserve(GMERGE.adj[u].size());
for (const auto& edge_info : GMERGE.adj[u]) {
int edge_id = edge_info.second;
if (edge_id >= 0 && edge_id <= max_id &&
in_C_edges_ws[edge_id]) {
R.push_back(G.get_edge_ptr(edge_id));
}
}
}
Path r = validate_separator(R, G, find_odd_S_sep, P_indices,
min_P_neighbor_index, adj_R_reusable,
in_R_reusable);
if (!r.empty()) {
X_result.push_back(r);
}
}
for (int32_t edge_id : C_edges) {
if (edge_id >= 0 && edge_id <= max_id)
in_C_edges_ws[edge_id] = false;
}
for (Vertex v : C_vertices_vec) {
in_C_vertices_ws[v] = false;
}
}
}
vector<Path> compute_X_ST(const Graph& G, const Path& P) {
vector<Path> X_ST;
compute_S_Separators(G, P, true, X_ST);
compute_S_Separators(G, P, false, X_ST);
Path P_rev = P;
reverse(P_rev.begin(), P_rev.end());
vector<Path> X_T;
compute_S_Separators(G, P_rev, true, X_T);
compute_S_Separators(G, P_rev, false, X_T);
for (Path& r : X_T) {
reverse(r.begin(), r.end());
X_ST.push_back(r);
}
sort(X_ST.begin(), X_ST.end());
X_ST.erase(unique(X_ST.begin(), X_ST.end()), X_ST.end());
return X_ST;
}
vector<Path> compute_X_EXTRA(const Graph& G, const Path& P0) {
if (P0.empty())
return {};
OptimizedSet<PackedKey> edges_P0_set;
vector<int64_t> P0_weights;
if (!P0.empty()) {
edges_P0_set.reserve(P0.size() - 1);
P0_weights.reserve(P0.size() - 1);
for (size_t i = 0; i < P0.size() - 1; ++i) {
edges_P0_set.insert(edge_key(P0[i], P0[i + 1]));
P0_weights.push_back(get_edge_length(G, P0[i], P0[i + 1]));
}
}
auto is_edge_on_P0 = [&](Vertex u, Vertex v) {
return edges_P0_set.count(edge_key(u, v));
};
vector<int32_t> component_id(G.N, 0);
int comp_count = 0;
queue<Vertex> q;
for (Vertex v = 1; v < G.N; ++v) {
if (component_id[v] == 0) {
comp_count++;
q.push(v);
component_id[v] = comp_count;
while (!q.empty()) {
Vertex u = q.front();
q.pop();
for (const auto& edge : G.adj[u]) {
Vertex neighbor = edge.to;
if (is_edge_on_P0(u, neighbor))
continue;
if (neighbor < G.N && component_id[neighbor] == 0) {
component_id[neighbor] = comp_count;
q.push(neighbor);
}
}
}
}
}
vector<int32_t> BEL(P0.size());
for (int32_t i = 0; i < static_cast<int32_t>(P0.size()); ++i) {
if (P0[i] < G.N)
BEL[i] = component_id[P0[i]];
}
vector<Path> X_EXTRA;
int32_t i = 0;
for (int32_t j = 1; j < static_cast<int32_t>(P0.size()); ++j) {
if (j > 1 && BEL[j] != BEL[j - 2]) {
if (i < j - 1) {
Path candidate;
vector<int64_t> candidate_weights;
for (int32_t k = i; k <= j - 1; ++k) {
candidate.push_back(P0[k]);
if (k < j - 1)
candidate_weights.push_back(P0_weights[k]);
}
if (candidate.size() >= 4 &&
is_useful_weighted(candidate, candidate_weights, G)) {
X_EXTRA.push_back(candidate);
}
}
i = j - 1;
}
if (j > 0 && BEL[j] == BEL[j - 1])
i = j;
}
if (i < static_cast<int32_t>(P0.size()) - 1) {
Path candidate;
vector<int64_t> candidate_weights;
for (int32_t k = i; k < static_cast<int32_t>(P0.size()); ++k) {
candidate.push_back(P0[k]);
if (k < static_cast<int32_t>(P0.size()) - 1)
candidate_weights.push_back(P0_weights[k]);
}
if (candidate.size() >= 4 &&
is_useful_weighted(candidate, candidate_weights, G)) {
X_EXTRA.push_back(candidate);
}
}
return X_EXTRA;
}
struct LR_Cache {
OptimizedMap<Vertex> L_cache;
OptimizedMap<Vertex> R_cache;
};
void compute_LR(const vector<Path>& X, const Graph& G,
const BCCFinder& bcc_finder, LR_Cache& cache) {
OptimizedMap<pair<int, int>> edge_X_info;
size_t total_edges_X = 0;
for (const auto& r : X)
total_edges_X += (r.size() > 0 ? r.size() - 1 : 0);
edge_X_info.reserve(total_edges_X);
cache.L_cache.reserve(total_edges_X * 2);
cache.R_cache.reserve(total_edges_X * 2);
for (int32_t r_id = 0; r_id < static_cast<int32_t>(X.size()); ++r_id) {
const Path& r = X[r_id];
for (int32_t i = 0; i < static_cast<int32_t>(r.size()) - 1; ++i) {
edge_X_info[edge_key(r[i], r[i + 1])] = {r_id, i};
}
}
vector<uint8_t> in_r(G.N, false);
auto is_in_BCC = [&](Vertex v, const OptimizedSet<Vertex>& bcc_vertices) {
return bcc_vertices.count(v);
};
for (int32_t r_id = 0; r_id < static_cast<int32_t>(X.size()); ++r_id) {
const Path& r = X[r_id];
for (Vertex v : r)
if (v < G.N)
in_r[v] = true;
for (int32_t i = 1; i < static_cast<int32_t>(r.size()) - 1; ++i) {
Vertex ri = r[i];
if (ri < G.N) {
for (const auto& edge : G.adj[ri]) {
Vertex u = edge.to;
if (u >= G.N || !in_r[u]) {
PackedKey current_edge_key = edge_key(u, ri);
auto it_edge_X = edge_X_info.find(current_edge_key);
bool edge_in_G_prime = (it_edge_X == edge_X_info.end());
Vertex L_val = ri;
if (i >= 2) {
Vertex ri_minus_2 = r[i - 2];
bool strongly_connected = false;
if (edge_in_G_prime) {
auto it_bcc = bcc_finder.edge_to_BCC.find(
current_edge_key);
if (it_bcc != bcc_finder.edge_to_BCC.end()) {
int32_t bcc_idx = it_bcc->second;
const auto& bcc = bcc_finder.BCCs[bcc_idx];
if (is_in_BCC(ri_minus_2, bcc)) {
strongly_connected = true;
}
}
} else {
auto info = it_edge_X->second;
int32_t r_prime_id = info.first;
const Path& r_prime = X[r_prime_id];
Vertex r_prime_2 = V_NONE;
bool valid_orientation = false;
if (r_prime.size() >= 3) {
if (ri == r_prime[0] && u == r_prime[1]) {
r_prime_2 = r_prime[2];
valid_orientation = true;
} else if (ri == r_prime.back() &&
u == r_prime[r_prime.size() -
2]) {
r_prime_2 = r_prime[r_prime.size() - 3];
valid_orientation = true;
}
}
if (valid_orientation) {
if (r_prime_2 < G.N && in_r[r_prime_2]) {
if (r_prime_2 == ri_minus_2) {
strongly_connected = true;
}
} else {
PackedKey chord_edge_key =
edge_key(r_prime_2, ri);
auto it_chord_bcc =
bcc_finder.edge_to_BCC.find(
chord_edge_key);
if (it_chord_bcc !=
bcc_finder.edge_to_BCC.end()) {
int32_t bcc_idx =
it_chord_bcc->second;
const auto& bcc =
bcc_finder.BCCs[bcc_idx];
if (is_in_BCC(ri_minus_2, bcc)) {
strongly_connected = true;
}
}
}
}
}
if (strongly_connected)
L_val = ri_minus_2;
}
cache.L_cache[lr_key(r_id, u)] = L_val;
Vertex R_val = ri;
if (i <= static_cast<int32_t>(r.size()) - 3) {
Vertex ri_plus_2 = r[i + 2];
bool strongly_connected = false;
if (edge_in_G_prime) {
auto it_bcc = bcc_finder.edge_to_BCC.find(
current_edge_key);
if (it_bcc != bcc_finder.edge_to_BCC.end()) {
int32_t bcc_idx = it_bcc->second;
const auto& bcc = bcc_finder.BCCs[bcc_idx];
if (is_in_BCC(ri_plus_2, bcc)) {
strongly_connected = true;
}
}
} else {
auto info = it_edge_X->second;
int32_t r_prime_id = info.first;
const Path& r_prime = X[r_prime_id];
Vertex r_prime_2 = V_NONE;
bool valid_orientation = false;
if (r_prime.size() >= 3) {
if (ri == r_prime[0] && u == r_prime[1]) {
r_prime_2 = r_prime[2];
valid_orientation = true;
} else if (ri == r_prime.back() &&
u == r_prime[r_prime.size() -
2]) {
r_prime_2 = r_prime[r_prime.size() - 3];
valid_orientation = true;
}
}
if (valid_orientation) {
if (r_prime_2 < G.N && in_r[r_prime_2]) {
if (r_prime_2 == ri_plus_2) {
strongly_connected = true;
}
} else {
PackedKey chord_edge_key =
edge_key(r_prime_2, ri);
auto it_chord_bcc =
bcc_finder.edge_to_BCC.find(
chord_edge_key);
if (it_chord_bcc !=
bcc_finder.edge_to_BCC.end()) {
int32_t bcc_idx =
it_chord_bcc->second;
const auto& bcc =
bcc_finder.BCCs[bcc_idx];
if (is_in_BCC(ri_plus_2, bcc)) {
strongly_connected = true;
}
}
}
}
}
if (strongly_connected)
R_val = ri_plus_2;
}
cache.R_cache[lr_key(r_id, u)] = R_val;
}
}
}
}
for (Vertex v : r)
if (v < G.N)
in_r[v] = false;
}
}
Path AVOID(const Graph& G, Vertex S, Vertex T, const vector<Path>& X,
const vector<uint8_t>& is_bad) {
vector<pair<int, int>> inner_vertex_map(G.N, {-1, -1});
OptimizedSet<PackedKey> X_heads_set;
X_heads_set.reserve(X.size());
for (int32_t r_id = 0; r_id < static_cast<int32_t>(X.size()); ++r_id) {
const Path& r = X[r_id];
if (r.size() >= 2) {
X_heads_set.insert(directed_edge_key(r[0], r[1]));
}
for (int32_t i = 1; i < static_cast<int32_t>(r.size()) - 1; ++i) {
if (r[i] < G.N) {
inner_vertex_map[r[i]] = {r_id, i};
}
}
}
OptimizedSet<PackedKey> edges_X_set;
size_t total_edges_X = 0;
for (const auto& r : X)
total_edges_X += (r.size() > 0 ? r.size() - 1 : 0);
edges_X_set.reserve(total_edges_X);
for (const auto& r : X) {
for (size_t i = 0; i < r.size() - 1; ++i) {
edges_X_set.insert(edge_key(r[i], r[i + 1]));
}
}
BCCFinder bcc_finder(G, &edges_X_set);
bcc_finder.find_BCCs();
LR_Cache lr_cache;
compute_LR(X, G, bcc_finder, lr_cache);
auto get_L = [&](int32_t r_id, Vertex u) {
PackedKey key = lr_key(r_id, u);
auto it = lr_cache.L_cache.find(key);
if (it != lr_cache.L_cache.end())
return it->second;
return V_NONE;
};
auto get_R = [&](int32_t r_id, Vertex v) {
PackedKey key = lr_key(r_id, v);
auto it = lr_cache.R_cache.find(key);
if (it != lr_cache.R_cache.end())
return it->second;
return V_NONE;
};
auto is_edge_on_X = [&](Vertex u, Vertex v) {
return edges_X_set.count(edge_key(u, v));
};
auto get_r_info = [&](Vertex u) {
if (u < G.N)
return inner_vertex_map[u];
return make_pair(-1, -1);
};
auto is_X_head = [&](Vertex u, Vertex v) {
return X_heads_set.count(directed_edge_key(u, v));
};
using G1Node = pair<Vertex, int>;
vector<array<vector<pair<G1Node, int64_t>>, 2>> adj_G1(G.N);
for (Vertex u = 1; u < G.N; ++u) {
adj_G1[u][0].reserve(G.adj[u].size());
adj_G1[u][1].reserve(G.adj[u].size());
for (const auto& edge : G.adj[u]) {
Vertex v = edge.to;
if (v >= G.N || v == 0)
continue;
int64_t w = edge.weight;
if ((!is_bad.empty() && u < static_cast<int32_t>(is_bad.size()) &&
is_bad[u]) ||
(!is_bad.empty() && v < static_cast<int32_t>(is_bad.size()) &&
is_bad[v]))
continue;
bool u_is_inner = (get_r_info(u).first != -1);
bool v_is_inner = (get_r_info(v).first != -1);
auto is_on_r = [&](Vertex node, int r_id) {
if (r_id < 0 || r_id >= static_cast<int32_t>(X.size()))
return false;
if (node < G.N && get_r_info(node).first == r_id)
return true;
const Path& r = X[r_id];
return !r.empty() && (node == r.front() || node == r.back());
};
bool transition_to_high = false;
if (v_is_inner) {
int r_id = get_r_info(v).first;
const Path& r = X[r_id];
int idx_v = get_r_info(v).second;
bool u_on_r = is_on_r(u, r_id);
if ((!u_on_r && idx_v == static_cast<int32_t>(r.size()) - 3) ||
(r.size() > 1 && u == r[0] && v == r[1])) {
transition_to_high = true;
}
}
if (transition_to_high) {
adj_G1[u][0].push_back({{v, 1}, w});
}
bool transition_to_low = true;
if (is_X_head(u, v)) {
transition_to_low = false;
}
if (v_is_inner && transition_to_low) {
int r_id = get_r_info(v).first;
bool u_on_r = is_on_r(u, r_id);
if (!u_on_r && get_L(r_id, u) == v) {
transition_to_low = false;
}
}
if (transition_to_low) {
adj_G1[u][0].push_back({{v, 0}, w});
}
if (u_is_inner) {
int r_id_u = get_r_info(u).first;
const Path& r_u = X[r_id_u];
int idx_u = get_r_info(u).second;
if (v_is_inner) {
bool transition_high_high = true;
int r_id_v = get_r_info(v).first;
if (r_id_u == r_id_v) {
if (idx_u >= 1 && v == r_u[idx_u - 1])
transition_high_high = false;
if (idx_u >= 2 && v == r_u[idx_u - 2])
transition_high_high = false;
} else {
if (get_R(r_id_u, v) == u)
transition_high_high = false;
}
if (transition_high_high) {
adj_G1[u][1].push_back({{v, 1}, w});
}
}
bool transition_high_low = true;
if (is_edge_on_X(u, v))
transition_high_low = false;
if (idx_u >= 2 && v == r_u[idx_u - 2])
transition_high_low = false;
bool v_on_ru = is_on_r(v, r_id_u);
if (!v_on_ru && get_R(r_id_u, v) == u)
transition_high_low = false;
if (v_is_inner) {
int r_id_v = get_r_info(v).first;
if (r_id_u != r_id_v && get_L(r_id_v, u) == v)
transition_high_low = false;
}
if (transition_high_low) {
adj_G1[u][1].push_back({{v, 0}, w});
}
}
}
}
G1Node StartNode = {S, 0};
G1Node EndNode = {T, 0};
vector<array<int64_t, 2>> dist(G.N, {INF, INF});
G1Node InvalidParent = {V_NONE, 0};
vector<array<G1Node, 2>> parent(G.N, {InvalidParent, InvalidParent});
using PQElementG1 = pair<int64_t, G1Node>;
priority_queue<PQElementG1, vector<PQElementG1>, greater<PQElementG1>> pq;
if (S >= G.N || T >= G.N || S == 0 || T == 0 ||
(!is_bad.empty() && S < static_cast<int32_t>(is_bad.size()) &&
is_bad[S]))
return {};
dist[S][0] = 0;
pq.push({0, StartNode});
int64_t shortest_dist = INF;
while (!pq.empty()) {
int64_t d = pq.top().first;
G1Node u_node = pq.top().second;
Vertex u = u_node.first;
int32_t state_u = u_node.second;
pq.pop();
if (d > dist[u][state_u])
continue;
if (u_node == EndNode) {
shortest_dist = d;
break;
}
for (const auto& edge_info : adj_G1[u][state_u]) {
G1Node v_node = edge_info.first;
Vertex v = v_node.first;
int32_t state_v = v_node.second;
int64_t weight = edge_info.second;
if (d + weight < dist[v][state_v]) {
dist[v][state_v] = d + weight;
parent[v][state_v] = u_node;
pq.push({dist[v][state_v], v_node});
}
}
}
if (shortest_dist == INF)
return {};
Path path_G;
G1Node curr = EndNode;
while (curr != StartNode) {
path_G.push_back(curr.first);
G1Node p = parent[curr.first][curr.second];
if (p.first == V_NONE)
break;
curr = p;
}
if (curr == StartNode)
path_G.push_back(StartNode.first);
reverse(path_G.begin(), path_G.end());
return path_G;
}
Path ShortestNonSeparatingPath(const Graph& G_input, Vertex S, Vertex T) {
if (S == T)
return {S};
Graph G_initial(G_input.N - 1, G_input.edge_list.size());
for (const auto* ptr : G_input.edge_list) {
G_initial.add_edge(ptr->u, ptr->v, ptr->weight, ptr->id, ptr);
}
BridgeFinder bf(G_initial);
bf.find_Bridges();
vector<int32_t> component_id(G_initial.N, 0);
int32_t comp_count = 0;
queue<Vertex> q;
for (Vertex v = 1; v < G_initial.N; ++v) {
if (component_id[v] == 0) {
comp_count++;
q.push(v);
component_id[v] = comp_count;
while (!q.empty()) {
Vertex u = q.front();
q.pop();
for (const auto& edge : G_initial.adj[u]) {
if (edge.id != -1 &&
edge.id < static_cast<int32_t>(bf.is_bridge.size()) &&
bf.is_bridge[edge.id])
continue;
Vertex neighbor = edge.to;
if (neighbor < G_initial.N && component_id[neighbor] == 0) {
component_id[neighbor] = comp_count;
q.push(neighbor);
}
}
}
}
}
if (S >= G_initial.N || T >= G_initial.N || S == 0 || T == 0 ||
component_id[S] != component_id[T] || component_id[S] == 0) {
return {};
}
Graph G_pre(G_initial.N - 1, G_initial.edge_list.size());
int32_t target_comp = component_id[S];
vector<int32_t> degrees(G_initial.N, 0);
for (const auto* ptr : G_initial.edge_list) {
if (ptr->u < G_initial.N && component_id[ptr->u] == target_comp &&
ptr->v < G_initial.N && component_id[ptr->v] == target_comp) {
degrees[ptr->u]++;
degrees[ptr->v]++;
}
}
for (int32_t i = 1; i < G_initial.N; ++i) {
if (i < G_pre.N) {
G_pre.adj[i].reserve(degrees[i]);
}
}
for (const auto* ptr : G_initial.edge_list) {
if (ptr->u < G_initial.N && component_id[ptr->u] == target_comp &&
ptr->v < G_initial.N && component_id[ptr->v] == target_comp) {
G_pre.add_edge(ptr->u, ptr->v, ptr->weight, ptr->id, ptr);
}
}
const Graph& G = G_pre;
vector<uint8_t> is_bad = compute_BAD_G(G, S, T);
pair<int64_t, Path> result_P = dijkstra(G, S, T, is_bad);
if (result_P.first == INF)
return {};
Path P = result_P.second;
vector<Path> X_ST = compute_X_ST(G, P);
vector<int32_t> P_indices = get_P_indices_vec(P, G.N);
vector<int32_t> forbidden_ids_vec;
int32_t max_id = -1;
auto find_edge_id = [&](Vertex u, Vertex v) {
if (u < G.N) {
for (const auto& edge : G.adj[u]) {
if (edge.to == v)
return edge.id;
}
}
return -1;
};
for (const Path& r : X_ST) {
if (r.size() < 4)
continue;
bool is_S_sep = true;
for (size_t i = 2; i < r.size(); ++i) {
if (r[i] >= G.N || P_indices[r[i]] == -1) {
is_S_sep = false;
break;
}
}
bool is_T_sep = true;
for (size_t i = 0; i <= r.size() - 3; ++i) {
if (r[i] >= G.N || P_indices[r[i]] == -1) {
is_T_sep = false;
break;
}
}
if (is_S_sep) {
int32_t id = find_edge_id(r[r.size() - 2], r[r.size() - 1]);
if (id != -1) {
forbidden_ids_vec.push_back(id);
max_id = max(max_id, id);
}
}
if (is_T_sep) {
int32_t id = find_edge_id(r[0], r[1]);
if (id != -1) {
forbidden_ids_vec.push_back(id);
max_id = max(max_id, id);
}
}
}
vector<uint8_t> G0_forbidden_edge_ids;
if (max_id != -1) {
G0_forbidden_edge_ids.resize(max_id + 1, false);
for (int32_t id : forbidden_ids_vec)
G0_forbidden_edge_ids[id] = true;
}
pair<int64_t, Path> result_P0 =
dijkstra(G, S, T, is_bad, G0_forbidden_edge_ids);
Path P0;
if (result_P0.first != INF)
P0 = result_P0.second;
vector<Path> X_EXTRA = compute_X_EXTRA(G, P0);
vector<Path> X = X_ST;
X.reserve(X_ST.size() + X_EXTRA.size());
X.insert(X.end(), X_EXTRA.begin(), X_EXTRA.end());
sort(X.begin(), X.end());
X.erase(unique(X.begin(), X.end()), X.end());
return AVOID(G, S, T, X, is_bad);
}
constexpr int __buffsize = 1 << 20;
char __buff[__buffsize];
char *__buffs = __buff, *__buffe = __buff;
inline char getc() {
if (__buffs == __buffe) {
size_t flywheel = fread(__buff, 1, __buffsize, stdin);
if (flywheel == 0)
return EOF;
__buffe = __buff + flywheel;
__buffs = __buff;
}
return *(__buffs++);
}
template <typename T> inline void read_number(T& x) {
x = 0;
static char c;
bool flag = false;
while ((c = getc()) != EOF && (c < '0' || c > '9') && c != '-')
;
if (c == EOF)
return;
if (c == '-') {
flag = true;
c = getc();
} else if (c >= '0' && c <= '9') {
x = c - '0';
c = getc();
}
while (c != EOF && c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c - '0');
c = getc();
}
if (flag)
x = -x;
}
inline void read_int(int32_t& x) { read_number<int32_t>(x); }
inline void read_long(int64_t& x) { read_number<int64_t>(x); }
int main() {
int32_t n, m;
read_int(n);
read_int(m);
struct InputEdge {
PackedKey key;
int64_t w;
bool operator<(const InputEdge& other) const {
if (key != other.key)
return key < other.key;
return w < other.w;
}
};
vector<InputEdge> input_edges;
if (m > 0)
input_edges.reserve(m);
for (int32_t i = 0; i < m; ++i) {
int32_t u, v;
int64_t w;
read_int(u);
read_int(v);
read_long(w);
if (u != v) {
PackedKey key = edge_key(u, v);
input_edges.push_back({key, w});
}
}
sort(input_edges.begin(), input_edges.end());
int32_t s, t;
read_int(s);
read_int(t);
int32_t unique_edge_count = 0;
vector<int32_t> degrees(n + 1, 0);
if (!input_edges.empty()) {
unique_edge_count = 1;
auto count_degree = [&](const InputEdge& edge) {
pair<Vertex, Vertex> uv = unpack_edge_key(edge.key);
if (uv.first <= n)
degrees[uv.first]++;
if (uv.second <= n)
degrees[uv.second]++;
};
count_degree(input_edges[0]);
for (size_t i = 1; i < input_edges.size(); ++i) {
if (input_edges[i].key != input_edges[i - 1].key) {
unique_edge_count++;
count_degree(input_edges[i]);
}
}
}
Graph G(n, unique_edge_count);
for (int32_t i = 1; i <= n && i < G.N; ++i) {
G.adj[i].reserve(degrees[i]);
}
int32_t edge_id_counter = 0;
if (!input_edges.empty()) {
auto add_edge_to_G = [&](const InputEdge& edge) {
pair<Vertex, Vertex> uv = unpack_edge_key(edge.key);
int64_t w = edge.w;
int32_t id = edge_id_counter++;
G.add_edge(uv.first, uv.second, w, id, nullptr);
};
add_edge_to_G(input_edges[0]);
for (size_t i = 1; i < input_edges.size(); ++i) {
if (input_edges[i].key != input_edges[i - 1].key) {
add_edge_to_G(input_edges[i]);
}
}
}
Path result = ShortestNonSeparatingPath(G, s, t);
if (result.empty()) {
printf("-1\n");
} else {
int64_t total_weight = 0;
for (size_t i = 0; i < result.size() - 1; ++i) {
total_weight += get_edge_length(G, result[i], result[i + 1]);
}
printf("%lld\n", (long long)total_weight);
}
return 0;
}
加载中...