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 $n$ vertices and atmost $n+20$ edges. Ask $q$ queries of calculating shortest path between $u_i$ and $v_i$.

**Constraints:** $1 \le m, n,q \le 10^5, \ m-n \le 20$

## Solution
First we can construct an **arbitrary** spanning tree, distance between $u$ and $v$ in this tree can be calculated by $d_u + d_v - 2\cdot d_{lca(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 $dis$, then check if $dis_u + dis_v$ 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)

コメント

コメントを投稿