ZOJ 3195 Design the city

Love The Way You Lie 2021-12-16 12:37 155阅读 0赞

[传送门][Link 1]

三个点之间的最短路径

答案就是两两lca之和除以2

注意输出格式。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <bits/stdc++.h>
    using namespace std;
    
    inline int read() {
        int x = 0, f = 1; char ch = getchar();
        while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar();}
        while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
        return x * f;
    }
    
    const int maxn = 5e4 + 10;
    const int maxm = 7e4 + 10;
    struct Edge { int v, c, next; } edge[maxn * 2];
    struct Qedge { int v, next, num, id; } qedge[maxm * 6];
    int cnt, head[maxn], qcnt, qhead[maxn], dep[maxn];
    int ans[maxm][4], n, m, par[maxn];
    bool vis[maxn];
    
    inline void addedge(int u, int v, int c) { 
        edge[++cnt].v = v; 
        edge[cnt].c = c; 
        edge[cnt].next = head[u]; 
        head[u] = cnt; 
    }
    inline void addqedge(int u, int v, int num, int id) { 
        qedge[++qcnt].v = v; 
        qedge[qcnt].next = qhead[u]; 
        qhead[u] = qcnt; 
        qedge[qcnt].num = num; 
        qedge[qcnt].id = id;
    }
    int getfa(int x) { return x == par[x] ? x : par[x] = getfa(par[x]); }
    void dfs(int u) {
        vis[u] = 1;
        par[u] = u;
        for (int i = head[u]; i; i = edge[i].next) {
            int v = edge[i].v;
            if (vis[v]) continue;
            dep[v] = dep[u] + edge[i].c;
            dfs(v);
            par[v] = u;
        }
        for (int i = qhead[u]; i; i = qedge[i].next) {
            int v = qedge[i].v;
            if (vis[v]) {
                int x = getfa(v);
                ans[qedge[i].id][qedge[i].num] = dep[u] + dep[v] - 2 * dep[x];  
            }
        }
    }
    
    int main() {
        int kase = 0;
        while (~scanf("%d", &n)) {
            memset(head, 0, sizeof(head));
            memset(qhead, 0, sizeof(qhead));
            cnt = qcnt = 0;
            memset(ans, 0, sizeof(ans));
            memset(vis, 0, sizeof(vis));
            for (int i = 0; i < n - 1; i++) {
                int u = read(), v = read(), c = read();
                addedge(u, v, c);
                addedge(v, u, c);
            }
            m = read();
            for (int i = 0; i < m; i++) {
                int u = read(), v = read(), w = read();
                addqedge(u, v, 0, i); addqedge(v, u, 0, i);
                addqedge(v, w, 1, i); addqedge(w, v, 1, i);
                addqedge(u, w, 2, i); addqedge(w, u, 2, i);
            }
            dfs(0);
            if (kase) puts(""); kase++;
            for (int i = 0; i < m; i++) printf("%d\n", (ans[i][0] + ans[i][1] + ans[i][2]) / 2);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Mrzdtz220/p/10777241.html

[Link 1]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3195
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211214/871c520f3d654833a4217837c1fb8be5.png