You are given a weighed undirected connected graph, consisting of 𝑛 vertices and 𝑚 edges.

You should answer 𝑞 queries, the 𝑖-th query is to find the shortest distance between vertices 𝑢𝑖 and 𝑣𝑖.

Input
The first line contains two integers 𝑛 and 𝑚 (1≤𝑛,𝑚≤105,𝑚−𝑛≤20) — the number of vertices and edges in the graph.

Next 𝑚 lines contain the edges: the 𝑖-th edge is a triple of integers 𝑣𝑖,𝑢𝑖,𝑑𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛,1≤𝑑𝑖≤109,𝑢𝑖≠𝑣𝑖). This triple means that there is an edge between vertices 𝑢𝑖 and 𝑣𝑖 of weight 𝑑𝑖. It is guaranteed that graph contains no self-loops and multiple edges.

The next line contains a single integer 𝑞 (1≤𝑞≤105) — the number of queries.

Each of the next 𝑞 lines contains two integers 𝑢𝑖 and 𝑣𝑖 (1≤𝑢𝑖,𝑣𝑖≤𝑛) — descriptions of the queries.

Pay attention to the restriction 𝑚−𝑛 ≤ 20.

Output
Print 𝑞 lines.

The 𝑖-th line should contain the answer to the 𝑖-th query — the shortest distance between vertices 𝑢𝑖 and 𝑣𝑖.

Examples
input

output

3
4
1

input

output

题目大意

给你一个图，这个图边数最多比点数多20，一共Q次询问两个点的最短距离，Q = 1e5

解法

因为边数只比点数多20个，看见20就认为是复杂度多了个log。

对于给定的数据，构建一棵树，构建一个图，对于图中有21条边不属于树上，所以最多有42个不同的点。将这41个点以源点跑41次最短路。

然后两个点的距离只有两种情况，要么只通过树上的唯一最短路径求得，要么是x到y的过程中经过了这42个其中的某一点 $ans = min(dist[x] + dist[y] - dist[lca],disg[i][x] + dis[i][y])$ i是42个点中的一个，循环就好

$dist[x]$ 为x到根节点的距离

$disg[i][x]$ 为i到x的最短距离

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e5+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int N,M,Q;
int h1[maxn],h2[maxn],e[4*maxn],w[4*maxn],ne[4*maxn],idx = 1;
int f[maxn],fa[maxn][22],dep[maxn];ll dist[maxn];
ll disg[45][maxn];bool vis[maxn];
int lisa[maxn],tail;
struct node
{
    ll u,w;
    bool operator <(const node &o) const{
        return w > o.w;
    }
};
priority_queue<node> q;
void add(int h[],int a,int b,int c){
    e[++idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx;
}
int find(int x){
    return x == f[x] ? x : f[x] = find(f[x]);
}
void init_lisa(){
    sort(lisa+1,lisa+tail+1);
    tail = unique(lisa+1,lisa+tail+1)-lisa-1;
}
int ind(int x){
    return lower_bound(lisa+1,lisa+tail+1,x)-lisa;
}
void init_tree(int u,int depth,ll len,int ff = -1){
    dep[u] = depth;
    for(int i = 1;i<=20;i++){
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for(int i = h1[u];i;i = ne[i]){
        int v = e[i],ww = w[i];
        if(v == ff) continue;
        fa[v][0] = u;
        dist[v] = len + ww;
        init_tree(v,depth + 1,len + ww,u);
    }
}
int lca(int a,int b){
    if(dep[a] < dep[b]) swap(a,b);
    for(int i = 20;i>=0;i--){
        if(dep[fa[a][i]] >= dep[b]){
            a = fa[a][i];
        }
    }
    if(a == b) return a;
    for(int i = 20;i>=0;i--){
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}
void dij(int s){
    int id = ind(s);
    for(int i = 1;i<=N;i++) disg[id][i] = inf2;
    for(int i = 1;i<=N;i++) vis[i] = 0;
    q.push({s,0});
    disg[id][s] = 0;

    while(q.size()){
        node cur = q.top();q.pop();
        int u = cur.u;
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = h2[u];i;i = ne[i]){
            int v = e[i];
            if(disg[id][u] + w[i] < disg[id][v]){
                disg[id][v] = disg[id][u] + w[i];
                q.push({v,disg[id][v]});
            }
        }
    }
}
int main(){
    // debug_in;

    read(N,M);
    for(int i = 1;i<=N;i++) f[i] = i;
    for(int i = 1;i<=M;i++){
        int a,b,c;read(a,b,c);
        int fx = find(a),fy = find(b);
        if(fx != fy){
            f[fx] = fy;
            add(h1,a,b,c);
            add(h1,b,a,c);
        }else{
            lisa[++tail] = a;
            lisa[++tail] = b;
        }
        add(h2,a,b,c);
        add(h2,b,a,c);
    }
    init_lisa();
    init_tree(1,1,0);
    for(int i = 1;i<=tail;i++) dij(lisa[i]);
    read(Q);
    while(Q--){
        int x,y;read(x,y);
        int lcaxy = lca(x,y);
        ll ans = dist[x] + dist[y] - 2 * dist[lcaxy];
        for(int i = 1;i<=tail;i++){
            ans = min(ans,disg[i][x] + disg[i][y]);
        }
        printf("%lld\n",ans);
    }



    return 0;
}

F. The Shortest Statement 【树，LCA，最短路】2400

题目大意

解法