Codeforces 1051F. The Shortest Statement (Shortest Path + LCA)

日付: 12月 20, 2018

[Problem - 1051F - Codeforces](https://codeforces.com/contest/1051/problem/F)
## Problem
Given a graph with <math><semantics><mrow><mi>n</mi></mrow><annotation encoding="application/x-tex">n</annotation></semantics></math>n vertices and atmost <math><semantics><mrow><mi>n</mi><mo>+</mo><mn>20</mn></mrow><annotation encoding="application/x-tex">n+20</annotation></semantics></math>n+20 edges. Ask <math><semantics><mrow><mi>q</mi></mrow><annotation encoding="application/x-tex">q</annotation></semantics></math>q queries of calculating shortest path between <math><semantics><mrow><msub><mi>u</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">u_i</annotation></semantics></math>ui and <math><semantics><mrow><msub><mi>v</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">v_i</annotation></semantics></math>vi.

**Constraints:** <math><semantics><mrow><mn>1</mn><mo>≤</mo><mi>m</mi><mo separator="true">,</mo><mi>n</mi><mo separator="true">,</mo><mi>q</mi><mo>≤</mo><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup><mo separator="true">,</mo><mtext> </mtext><mi>m</mi><mo>−</mo><mi>n</mi><mo>≤</mo><mn>20</mn></mrow><annotation encoding="application/x-tex">1 \le m, n,q \le 10^5, \ m-n \le 20</annotation></semantics></math>1≤m,n,q≤105, m−n≤20

## Solution
First we can construct an **arbitrary** spanning tree, distance between <math><semantics><mrow><mi>u</mi></mrow><annotation encoding="application/x-tex">u</annotation></semantics></math>u and <math><semantics><mrow><mi>v</mi></mrow><annotation encoding="application/x-tex">v</annotation></semantics></math>v in this tree can be calculated by <math><semantics><mrow><msub><mi>d</mi><mi>u</mi></msub><mo>+</mo><msub><mi>d</mi><mi>v</mi></msub><mo>−</mo><mn>2</mn><mo>⋅</mo><msub><mi>d</mi><mrow><mi>l</mi><mi>c</mi><mi>a</mi><mo>(</mo><mi>u</mi><mo separator="true">,</mo><mi>v</mi><mo>)</mo></mrow></msub></mrow><annotation encoding="application/x-tex">d_u + d_v - 2\cdot d_{lca(u,v)}</annotation></semantics></math>du+dv−2⋅dlca(u,v). And LCA can be solved by **tarjan's offline LCA algorithm**, which is as follows
```c++
DSU uf(N);
int An[N], Vis[N];
void tarjan(int u) {
 An[u] = u, Vis[u] = 2;
 for (auto v: G[u]) if (!Vis[v]) {
 tarjan(v);
 uf.unite(u, v);
 An[uf.root(u)] = u;
 }
 Vis[u] = 1;
 for each v that {u, v} is a query {
 if (Vis[v] == 1) 
 Ans[{u, v}] = An[uf.root(v)];
 }
}
```
Then iterate on the edges that is not used by the spanning tree, do dijkstra or spfa from one of its incident vertice. This is to find the shortest path that may use this edge. The result array is <math><semantics><mrow><mi>d</mi><mi>i</mi><mi>s</mi></mrow><annotation encoding="application/x-tex">dis</annotation></semantics></math>dis, then check if <math><semantics><mrow><mi>d</mi><mi>i</mi><msub><mi>s</mi><mi>u</mi></msub><mo>+</mo><mi>d</mi><mi>i</mi><msub><mi>s</mi><mi>v</mi></msub></mrow><annotation encoding="application/x-tex">dis_u + dis_v</annotation></semantics></math>disu+disv is shorter than distance on the tree.

## Code
```c++
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
#define FI(i,a,b) for(int i=(a);i<=(b);++i)

struct DSU {
 vector<int> F;
 DSU(int n): F(n, -1) {}
 int root(int x) { return F[x] < 0 ? x : F[x] = root(F[x]); }
 int size(int x) { return -F[root(x)]; }
 bool same(int x, int y) { return root(x) == root(y); }
 bool unite(int x, int y) {
 x = root(x), y = root(y);
 if (x != y) { if (F[y] < F[x]) swap(x, y); F[x] += F[y], F[y] = x; }
 return x != y;
 }
};
const int N = 1e5 + 35;
struct Edge { int u, v, d; } E[N * 2];
int n, m, q, te = 0, In[N], Use[N * 2], An[N];
LL Ans[N], Dis[N];
vector<int> G[N];
vector<PII> Q[N];
DSU uf(N);

void dfs(int u, LL dis) {
    Dis[u] = dis, In[u] = 2, An[u] = u;
    for (auto i : G[u]) {
        int v = E[i].v, d = E[i].d;
        if (In[v]) continue;
        Use[i] = 1;
        dfs(v, dis + d);
        uf.unite(u, v);
        An[uf.root(u)] = u;
    }
    In[u] = 1;
    for (auto [v, i] : Q[u]) {
        if (In[v]) Ans[i] = min(Ans[i], Dis[u] + Dis[v] - 2 * Dis[An[uf.root(v)]]);
    }
}

void spfa(int u) {
 memset(Dis, 10, sizeof Dis);
 memset(In, 0, sizeof In);
 queue<int> Qu;
 Dis[u] = 0, Qu.push(u), In[u] = 1;
 while (!Qu.empty()) {
 int u = Qu.front();
 Qu.pop(), In[u] = 0;
 for (auto i : G[u]) {
 int v = E[i].v, d = E[i].d;
 if (Dis[u] + d < Dis[v]) {
 Dis[v] = Dis[u] + d;
 if (!In[v]) Qu.push(v), In[v] = 1;
 }
 }
 }
 FI(u, 1, n) for (auto [v, i] : Q[u]) Ans[i] = min(Ans[i], Dis[u] + Dis[v]);
}

int main() {
 memset(Ans, 10, sizeof Ans);
 scanf("%d%d", &n, &m);
 FI(i, 1, m) {
 int u, v, d;
 scanf("%d%d%d", &u, &v, &d);
 G[u].push_back(te), E[te++] = {u, v, d};
 G[v].push_back(te), E[te++] = {v, u, d};
 }
 scanf("%d", &q);
 FI(i, 1, q) {
 int u, v;
 scanf("%d%d", &u, &v);
 Q[u].emplace_back(v, i);
 Q[v].emplace_back(u, i);
 }
 dfs(1, 0);
 vector<int> I;
 FI(i, 0, te - 1) if (!Use[i ^ 1] && !Use[i]) I.push_back(i), Use[i] = 1;
 assert(I.size() < 50);
 for (auto i : I) spfa(E[i].u);
 FI(i, 1, q) printf("%lld\n", Ans[i]);
}
```

KONGROOの基地

このブログを検索

Codeforces 1051F. The Shortest Statement (Shortest Path + LCA)

コメント

コメントを投稿