結果
| 問題 | No.1600 Many Shortest Path Problems |
| コンテスト | |
| ユーザー |
 limbo
|
| 提出日時 | 2025-12-12 21:20:15 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.89.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 8,122 bytes |
| 記録 | |
| コンパイル時間 | 1,084 ms |
| コンパイル使用メモリ | 91,888 KB |
| 実行使用メモリ | 26,148 KB |
| 最終ジャッジ日時 | 2025-12-12 21:20:32 |
| 合計ジャッジ時間 | 16,594 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 3 |
| other | TLE * 1 -- * 50 |
ソースコード
/**
* Title: Everything Everywhere All at Once
* Author: [Your Name/Handle]
* Complexity: O(M log M + Q log N)
* * Approach:
* 1. Since costs are 2^C_i and all C_i are distinct, the MST is unique.
* Any shortest path in the full graph is simply the path on the MST.
* 2. If the "glitched" edge K is NOT in the MST, the path remains the MST path.
* 3. If edge K IS in the MST:
* - If K is not on the path between A and B, the answer is still the MST path.
* - If K is on the path, removing it splits the MST into two components.
* We must cross between these components using the cheapest non-MST edge.
* 4. We precalculate the "best replacement edge" for every edge in the MST using
* a DSU-based offline approach (simulating Kruskal's for the second-best edge).
*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
// --- Constants & Utilities ---
const int MOD = 1e9 + 7;
const int MAXN = 200005;
const int LOGN = 20;
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
// --- Data Structures ---
struct Edge {
int u, v, id;
int c; // Exponent cost
long long weight_mod; // 2^c % MOD
bool in_mst;
// Sort by exponent C (greedy property)
bool operator<(const Edge& other) const {
return c < other.c;
}
};
struct DSU {
vector<int> parent;
DSU(int n) {
parent.resize(n + 1);
iota(parent.begin(), parent.end(), 0);
}
int find(int i) {
if (parent[i] == i) return i;
return parent[i] = find(parent[i]);
}
void unite(int i, int j) {
int root_i = find(i);
int root_j = find(j);
if (root_i != root_j) {
parent[root_i] = root_j;
}
}
};
// --- Globals ---
vector<Edge> edges;
vector<pair<int, int>> adj[MAXN]; // MST Adjacency list: {neighbor, edge_index}
int depth[MAXN], up[MAXN][LOGN];
int tin[MAXN], tout[MAXN], timer;
long long dist_from_root[MAXN]; // Sum of weights from root mod MOD
int edge_index_to_parent[MAXN]; // ID of the edge connecting u to parent[u]
// For replacement logic
int replacement_edge_idx[MAXN]; // Best replacement for the edge at index i
DSU* dsu_cover; // To track covered path segments
// --- MST & Tree Processing ---
void dfs(int u, int p, int edge_id_from_parent, long long current_dist) {
tin[u] = ++timer;
depth[u] = depth[p] + 1;
up[u][0] = p;
dist_from_root[u] = current_dist;
edge_index_to_parent[u] = edge_id_from_parent;
for (int i = 1; i < LOGN; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
for (auto& edge : adj[u]) {
int v = edge.first;
int id = edge.second;
if (v != p) {
long long w = edges[id].weight_mod;
dfs(v, u, id, (current_dist + w) % MOD);
}
}
tout[u] = ++timer;
}
bool is_ancestor(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int get_lca(int u, int v) {
if (is_ancestor(u, v)) return u;
if (is_ancestor(v, u)) return v;
for (int i = LOGN - 1; i >= 0; i--) {
if (!is_ancestor(up[u][i], v)) {
u = up[u][i];
}
}
return up[u][0];
}
// Distance on MST
long long get_path_cost(int u, int v) {
int lca = get_lca(u, v);
long long res = (dist_from_root[u] + dist_from_root[v]) % MOD;
long long sub = (2 * dist_from_root[lca]) % MOD;
return (res - sub + MOD) % MOD;
}
// --- Main Logic ---
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M, Q;
if (!(cin >> N >> M >> Q)) return 0;
edges.resize(M + 1); // 1-based indexing for convenience
for (int i = 1; i <= M; i++) {
edges[i].id = i;
cin >> edges[i].u >> edges[i].v >> edges[i].c;
edges[i].weight_mod = power(2, edges[i].c);
edges[i].in_mst = false;
}
// Sort edges to build MST (Kruskal's)
// We need a copy or a pointer array to sort, because queries reference original indices K
vector<int> sorted_indices(M);
iota(sorted_indices.begin(), sorted_indices.end(), 1);
sort(sorted_indices.begin(), sorted_indices.end(), [](int i, int j) {
return edges[i].c < edges[j].c;
});
DSU dsu_mst(N);
int edges_count = 0;
for (int idx : sorted_indices) {
if (dsu_mst.find(edges[idx].u) != dsu_mst.find(edges[idx].v)) {
dsu_mst.unite(edges[idx].u, edges[idx].v);
edges[idx].in_mst = true;
adj[edges[idx].u].push_back({edges[idx].v, idx});
adj[edges[idx].v].push_back({edges[idx].u, idx});
edges_count++;
}
}
// Build LCA and Tree properties
// Note: Graph is guaranteed connected, so node 1 is always a valid root
dfs(1, 1, -1, 0);
// --- Precalculate Replacement Edges ---
// We process NON-MST edges from smallest weight to largest.
// For a non-MST edge (u, v), it covers the path u-v in the MST.
// Any MST edge on this path that hasn't been covered yet gets this edge as its best replacement.
fill(replacement_edge_idx, replacement_edge_idx + M + 1, -1);
dsu_cover = new DSU(N); // Used to skip over already-covered edges on the tree
for (int idx : sorted_indices) {
if (!edges[idx].in_mst) {
int u = edges[idx].u;
int v = edges[idx].v;
// Find path using DSU to jump up
u = dsu_cover->find(u);
v = dsu_cover->find(v);
while (u != v) {
// We always move the deeper node up
if (depth[u] < depth[v]) swap(u, v);
// Now u is deeper. The edge above u is candidate for replacement
int edge_above = edge_index_to_parent[u];
if (edge_above != -1) {
if (replacement_edge_idx[edge_above] == -1) {
replacement_edge_idx[edge_above] = idx;
}
}
// Contract u into its parent
dsu_cover->parent[u] = dsu_cover->find(up[u][0]);
u = dsu_cover->find(u);
}
}
}
// --- Process Queries ---
for (int j = 0; j < Q; j++) {
int A, B, K;
cin >> A >> B >> K;
long long base_dist = get_path_cost(A, B);
if (!edges[K].in_mst) {
// Case 1: Removed edge is not in MST. Shortest path is unchanged.
cout << base_dist << "\n";
} else {
// Case 2: Removed edge is in MST.
// Check if edge K is on the path between A and B.
int u = edges[K].u;
int v = edges[K].v;
// Ensure v is the child in the tree structure (deeper node)
if (depth[u] > depth[v]) swap(u, v);
// K is on the path A-B if exactly one of A or B is in the subtree of v
bool a_in_sub = is_ancestor(v, A);
bool b_in_sub = is_ancestor(v, B);
if (a_in_sub == b_in_sub) {
// Both in subtree or both outside -> K is not on the simple path A-B
cout << base_dist << "\n";
} else {
// K is on the path. We must use the replacement edge.
int rep_idx = replacement_edge_idx[K];
if (rep_idx == -1) {
// No replacement edge exists (bridge) -> Disconnected
cout << "-1\n";
} else {
long long cost_removed = edges[K].weight_mod;
long long cost_added = edges[rep_idx].weight_mod;
long long ans = (base_dist - cost_removed + cost_added) % MOD;
ans = (ans + MOD) % MOD; // Handle negative result
cout << ans << "\n";
}
}
}
}
return 0;
}