首页 > 其他分享 >NC23482 小A的最短路

NC23482 小A的最短路

时间:2023-06-21 10:55:57浏览次数:42  
标签:NC23482 src int 短路 cin dep vector LCA

题目链接

题目

题目描述

小A这次来到一个景区去旅游,景区里面有N个景点,景点之间有N-1条路径。小A从当前的一个景点移动到下一个景点需要消耗一点的体力值。但是景区里面有两个景点比较特殊,它们之间是可以直接坐观光缆车通过,不需要消耗体力值。而小A不想走太多的路,所以他希望你能够告诉它,从当前的位置出发到他想要去的那个地方,他最少要消耗的体力值是多少。

输入描述

第一行一个整数N代表景区的个数。
接下来N-1行每行两个整数u,v代表从位置u到v之间有一条路径可以互相到达。
接下来的一行两个整数U,V表示这两个城市之间可以直接坐缆车到达。
接下来一行一个整数Q,表示有Q次询问。
接下来的Q行每行两个整数x,y,代表小A的位置在x,而他想要去的地方是y。

输出描述

对于每个询问下x,y输出一个结果,代表x到y消耗的最少体力对于每个询问下x,y输出一个结果,代表x到y消耗的最少体力对于每个询问下x,y输出一个结果,代表x到y消耗的最少体力

示例1

输入

4
1 2
1 3
2 4
3 4
2
1 3
3 4

输出

1
0

备注

\(1\leq N \leq 5e5, \space1 \leq Q\leq2e6\)

题解

方法一

知识点:倍增,LCA。

考虑用倍增LCA,有三种情况:

  1. \(u \to v\) 。
  2. \(u \to x \to y \to v\) 。
  3. \(u \to y \to x \to v\) 。

取最小值即可。

时间复杂度 \(O(n+q\log n)\)

空间复杂度 \(O(n\log n)\)

方法二

知识点:DFS序,LCA,ST表。

LCA也可以由欧拉序+ST表实现。

时间复杂度 \(O(n\log n + q)\)

空间复杂度 \(O(n\log n)\)

代码

方法一

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5e5 + 7;
vector<int> g[N];
int dep[N], f[27][N];

void dfs(int u, int fa) {
    f[0][u] = fa;
    dep[u] = dep[fa] + 1;
    for (int i = 1;i <= 20;i++)  f[i][u] = f[i - 1][f[i - 1][u]];
    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
    }
}

int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20;i >= 0;i--) {
        if (dep[f[i][u]] >= dep[v]) u = f[i][u];
        if (u == v) return u;
    }
    for (int i = 20;i >= 0;i--) {
        if (f[i][u] != f[i][v]) {
            u = f[i][u];
            v = f[i][v];
        }
    }
    return f[0][u];
}

int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n - 1;i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);

    int x, y;
    cin >> x >> y;

    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << min({ dist(u, v),dist(u,x) + dist(y,v),dist(u,y) + dist(x,v) }) << '\n';
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

template<class T>
class ST {
    vector<vector<T>> node;
public:
    ST() {}
    ST(const vector<T> &src) { init(src); }

    void init(const vector<T> &src) {
        assert(src.size());
        int n = src.size() - 1;
        int sz = log2(n);
        node.assign(sz + 1, vector<T>(n + 1));
        for (int i = 1;i <= n;i++) node[0][i] = src[i];
        for (int i = 1;i <= sz;i++)
            for (int j = 1;j + (1 << i) - 1 <= n;j++)
                node[i][j] = node[i - 1][j] + node[i - 1][j + (1 << i - 1)];
    }

    T query(int l, int r) {
        int k = log2(r - l + 1);
        return node[k][l] + node[k][r - (1 << k) + 1];
    }
};

const int N = 5e5 + 7;
vector<int> g[N];

int eulcnt;
int pos[N], eul[N << 1], dep[N];
void dfs(int u, int fa) {
    eul[++eulcnt] = u;
    pos[u] = eulcnt;
    dep[u] = dep[fa] + 1;
    for (auto v : g[u]) {
        if (v == fa) continue;
        dfs(v, u);
        eul[++eulcnt] = eul[pos[u]];
    }
}

struct T {
    int mi;
    friend T operator+(const T &a, const T &b) { return { dep[a.mi] < dep[b.mi] ? a.mi : b.mi }; }
};

ST<T> st;
int LCA(int u, int v) {
    u = pos[u], v = pos[v];
    if (u > v) swap(u, v);
    return st.query(u, v).mi;
}

int dist(int u, int v) { return dep[u] + dep[v] - 2 * dep[LCA(u, v)]; }

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1;i <= n - 1;i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 0);
    vector<T> eul_src(eulcnt + 1);
    for (int i = 1;i <= eulcnt;i++) eul_src[i] = { eul[i] };
    st.init(eul_src);

    int x, y;
    cin >> x >> y;

    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << min({ dist(u, v),dist(u,x) + dist(y,v),dist(u,y) + dist(x,v) }) << '\n';
    }
    return 0;
}

标签:NC23482,src,int,短路,cin,dep,vector,LCA
From: https://www.cnblogs.com/BlankYang/p/17495697.html

相关文章

  • abc051 <多源最短路>
    https://atcoder.jp/contests/abc051/tasks/abc051_d//https://atcoder.jp/contests/abc051/tasks/abc051_d//一条边不含于任何一条最短路中,当且仅当w[i][j]>dist[i][j],即存在一条最短路的权比这条边的权小#include<iostream>#include<algorithm>#include<cstrin......
  • 6-3 最短路径(弗洛伊德算法)
    #include<iostream>usingnamespacestd;#defineMaxInt32767#defineMVNum100typedefcharVerTexType;typedefintArcType;intPath[MVNum][MVNum];//标志两个结点之间是否可达intD[MVNum][MVNum];//存储两个结点间的边的权重typedefstruct{VerTexT......
  • P3371 【模板】单源最短路径(弱化版)(C++_SPFA算法_链式向前星)
    题目背景本题测试数据为随机数据,在考试中可能会出现构造数据让SPFA不通过,如有需要请移步P4779。题目描述如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。输入格式第一行包含三个整数n,m,s,分别表示点的个数、有向边的个数、出发点的编号。接下来m行每行包含三个......
  • 考前复习——最短路
    Floyd十分暴力方便的最短路算法虽然复杂度较高,但好在有最短路的图都可以用它解决(即无负环)intn,m;//n个节点m条边intmp[N][N];voidinit_floyd(){ for(inti=1;i<=n;i++) { for(intj=1;j<=n;j++) { mp[i][j]=Inf; } mp[i][i]=0; }}voidfloyd(){ fo......
  • 《交通规划》——python实现最短路分配方法
    《交通规划》——最短路分配方法说明:下面内容,将用python、networkx实现刘博航、杜胜品主编的《交通规划》P198页的例题,主要是实现最短路径分配方法。1.题目描述如下:2.networkx构建网络importnetworkxasnximportmatplotlib.pyplotasplt#带权重的边列表edges=[......
  • 「学习笔记」严格次短路
    出题人说:“有最短路,还要有次短路。”于是,就有了次短路这个东西。与次小生成树一样,目前不知道有啥用。本文求的是严格次短路!变量n:点数;m:边数;e:vector存图;dis1:储存最短路;dis2:储存次短路。过程我们要利用dijkstra的贪心思想和松弛操作。dijkstra的贪心思想,就是用目前路......
  • hdu2066 一个人的旅行(最短路)
    思路:简单最短路#include<stdio.h>#include<string.h>#include<algorithm>usingnamespacestd;constintinf=1<<30;intT,S,D,n;intmap[1111][1111];intvis[1111],cast[1111];ints[1111],e[1111];voidDijkstra(){inti,j,minn,p......
  • 算法——最短路径算法(dijkstra)
    source源端,target目的端1.构造n*n的相邻矩阵,-1表示未相邻intmatrix[n][n]intdist[n]初始化各节点直接到source的距离,dist[source]=0;boolvisited[n]是否访问过dist[source]=0;for(inti=0;i<n-1;i++){//找剩余n-1个节点的距离in......
  • m基于ENM-LAP模型的自组织网络平均最短路径长度matlab仿真分析
    1.算法仿真效果matlab2022a仿真结果如下:2.算法涉及理论知识概要移动自组织网络不但具有终端能量受限、无线信道状况受链路距离影响等特点,还具有节点位置的选择存在偏好的规律。本节建立基于节点位置偏好的网络拓扑演进模型,并利用复杂网络理论对其进行分析。网络拓扑结构产生过......
  • bzoj1001 [BeiJing2006]狼抓兔子(网络流dinic算法||最短路spfa)
    http://www.lydsy.com/JudgeOnline/problem.php?id=10011001:[BeiJing2006]狼抓兔子TimeLimit: 15Sec  MemoryLimit: 162MBSubmit: 24017  Solved: 6068[Submit][Status][Discuss]Description现在小朋友们最喜欢的"喜羊羊与灰太狼",话说灰太狼抓羊不到,但抓......