Codeforces 1051F(最短路+生成树+树图结合)

发表于 | 分类于 | | + s

Codeforces 1051F
题意：给出一个边比点数多至多$20$条的无向连通图，每条边有一个边权，多次询问两点间最短路。
由于特殊条件，我们可以随便建一棵生成树(又称 DFS 树)，然后就会只有最多$20$条边不在树中。
对于每个二元组询问$(u,v)$，我们答案有两种情况：
1、只走树上的边
2、必须经过一条树外的边
对于第一个很容易用 LCA 求出来。对于第二个，我们记录这条边的一个顶点$i$，然后用 dij 求出顶点的单源最短路，必走这条边的代价等价于$dis(i,u)+dis(i,v)$，因为这样的路径$(u,v)$就能覆盖这条边。两个情况取最小值即可。
知识点：
1、这种有特殊性题目可以将图转化为树，noip 货车运输是同样的思想，区别在于本题是随便一个生成树( DFS 树)，而 noip 那题是要最小生成树
2、本题也一定程度上与 相同，最短路之后枚举边求解

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const LL MAXN = 100000 + 5, LOGS = 17, INF = 300000000000005ll;

struct edge {LL u, v, d;};
struct data {
    LL u, d;
    bool operator < (const data &b) const {return d > b.d;}
};

std::vector<edge > G[MAXN];
std::set<std::pair<LL, LL> > nt;
std::priority_queue<data > q;
LL n, m, Q, vis[MAXN], dep[MAXN], pre[MAXN][30], h[MAXN], dis[50][MAXN];

void dfs(LL u, LL fa) {
    dep[u] = dep[fa] + 1, vis[u] = 1, pre[u][0] = fa;
    for (LL i = 1; i <= LOGS; i++) pre[u][i] = pre[pre[u][i - 1]][i - 1];
    for (LL i = 0; i < (LL)G[u].size(); i++) {
        edge &e = G[u][i];
        if (e.v != fa && !vis[e.v]) {
            h[e.v] = h[u] + e.d;
            dfs(e.v, u);
            if (u < e.v) nt.erase(std::make_pair(u, e.v)); else nt.erase(std::make_pair(e.v, u));
        }
    }
}
void dij(LL st, LL d[MAXN]) {
    for (LL i = 0; i <= n; i++) d[i] = INF, vis[i] = 0;
    d[st] = 0, q.push((data){st, 0});
    while (!q.empty()) {
        data p = q.top(); q.pop();
        if (vis[p.u]) continue; vis[p.u] = 1;
        for (LL i = 0; i < (LL)G[p.u].size(); i++) {
            edge &e = G[p.u][i];
            if (d[e.v] > d[p.u] + e.d) d[e.v] = d[p.u] + e.d, q.push((data){e.v, d[e.v]});
        }
    }
}
LL LCA(LL a, LL b) {
    if (dep[a] < dep[b]) std::swap(a, b);
    for (LL i = LOGS; i >= 0; i--) if (dep[pre[a][i]] >= dep[b]) a = pre[a][i];
    if (a == b) return a;
    for (LL i = LOGS; i >= 0; i--) if (pre[a][i] != pre[b][i]) a = pre[a][i], b = pre[b][i];
    return pre[a][0];
}
LL getdist(LL u, LL v) {return h[u] + h[v] - 2 * h[LCA(u, v)];}

void clean() {
    ms(h, 0), ms(vis, 0), ms(dep, 0);
}
int solve() {
    clean();
    for (LL u, v, d, i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &u, &v, &d);
        G[u].push_back((edge){u, v, d}), G[v].push_back((edge){v, u, d});
        if (u < v) nt.insert(std::make_pair(u, v)); else nt.insert(std::make_pair(v, u));
    }
    dfs(1, 0);
    //for (LL i = 0; i < (LL)nt.size(); i++) printf("u=%lld v=%lld d=%lld\n", nt[i].u, nt[i].v, nt[i].d);
    LL cnt = 0;
    for (std::set<std::pair<LL, LL> >::iterator it = nt.begin(); it != nt.end(); it++) {
        std::pair<LL, LL> e = *it;
        LL &u = e.first, &v = e.second;
        //printf("u=%lld v=%lld d=%lld\n", nt[i].u, nt[i].v, nt[i].d);
        if (u > v) continue;
        dij(u, dis[++cnt]);
    }
    //for (LL i = 1; i <= n; i++) for (LL j = 1; j <= n; j++) printf("i=%lld j=%lld lca=%lld\n", i, j, LCA(i, j));
    scanf("%lld", &Q);
    while (Q--) {
        LL u, v; scanf("%lld%lld", &u, &v);
        LL ans = getdist(u, v);
        for (LL i = 1; i <= cnt; i++) {
            ans = std::min(ans, dis[i][u] + dis[i][v]);
        }
        printf("%lld\n", ans);
    }
    return 0; 
}
int main() {
    scanf("%lld%lld", &n, &m), solve();
    return 0;
}
------ 本文结束 ------