cf 1051F The Shortest Statement

一 原题

F. The Shortest Statement

time limit per test: 4 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given a weighed undirected connected graph, consisting of nn vertices and mm edges.

You should answer qq queries, the ii-th query is to find the shortest distance between vertices uiui and vivi.

Input

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

Next mm lines contain the edges: the ii-th edge is a triple of integers vi,ui,di (1≤ui,vi≤n,1≤di≤109,ui≠vi)vi,ui,di (1≤ui,vi≤n,1≤di≤109,ui≠vi). This triple means that there is an edge between vertices uiui and vivi of weight didi. It is guaranteed that graph contains no self-loops and multiple edges.

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

Each of the next qq lines contains two integers uiui and vi (1≤ui,vi≤n)vi (1≤ui,vi≤n) — descriptions of the queries.

Pay attention to the restriction m−n ≤ 20m−n ≤ 20.

Output

Print qq lines.

The ii-th line should contain the answer to the ii-th query — the shortest distance between vertices uiui and vivi.

Examples

input

Copy

3 3
1 2 3
2 3 1
3 1 5
3
1 2
1 3
2 3

output

Copy

3
4
1
二 分析

给你一个有1e5顶点的无向连通图,图里的边数最多比定点数多20。要处理1e5次查询,每次查询给定图上的两个点,返回这两个点的最短路长度。

如果没有边数的限制,那只能跑dijkstra或floyd。有这个限制的话,这个图就非常接近一棵树。树上两个点的简单路径是唯一的,求一下lca就可以了。但是生成树外最多还有20+1条边,把这些边的顶点记在一个集合里。如果最优解需要用到生成树之外的边,那么最短路径一定经过集合中的某个点,预处理时对这最多42个点各跑一次dijkstra。预处理lca复杂度O(nlgn),一次dijkstra复杂度O(nlgn+m)。单次查询复杂度是求lca的O(lgn)。

还真没见过一道CF题要写三个基础算法:并查集求生成树,最短路,LCA。。

 

三 代码
/*=====================================
*   
*   AUTHOR : maxkibble
*   CREATED: 2018.09.29 10:52:24
*
=====================================*/


#include bits/stdc++.h

using namespace std;

#define fi first
#define se second
#define pb push_back

typedef long long ll;
typedef pairint, int pii;
typedef pairlong long, int pli;

const int maxn = 1e5 + 5;
const int maxd = 20;
const int maxc = 45;
const ll inf = 1e15;

int n, m;
bool use[maxn];
int dep[maxn];
ll dis[maxn];
ll dijk_dis[maxc][maxn]; int cnt = 0;
int fa[maxd][maxn];
vectorpii a[maxn];

struct Edge {
  int fr, to, len;
};

struct DSU {
  vectorint f;
  setint st;
  
  DSU(int num) {
    for (int i = 0; i = num; i++) f.pb(i);
  }
  
  int getF(int x) {
    return f[x] == x? x: f[x] = getF(f[x]);
  }
  
  void add(int x, int y, int i) {
    int fx = getF(x), fy = getF(y);
    if (fx == fy) {
      st.insert(x);
      st.insert(y);
    } else {
      if (fx  fy) swap(fx, fy);
      f[fy] = fx;
      use[i] = true;
    }
  }
};

void dfs(int cur, int pre, int distance) {
  dep[cur] = dep[pre] + 1;
  dis[cur] = dis[pre] + distance;
  fa[0][cur] = pre;
  for (auto nxt: a[cur]) {
    if (nxt.fi == pre) continue;
    dfs(nxt.fi, cur, nxt.se);
  }
}

int lca(int x, int y) {
  if (dep[x]  dep[y]) swap(x, y);
  int i = 0, d = dep[x] - dep[y];
  while (d) {
    if (d  1) x = fa[i][x];
    i++;
    d = 1;
  }
  if (x == y) return x;
  for (int i = maxd - 1; i = 0; i--) {
    if (fa[i][x] != fa[i][y]) {
      x = fa[i][x];
      y = fa[i][y];
    }
  }
  return fa[0][x];
}

void dijkstra(int st) {
  for (int i = 1; i = n; i++) {
    dijk_dis[cnt][i] = inf;
  }
  dijk_dis[cnt][st] = 0;
  priority_queuepli, vectorpli, greaterpli q;
  for (auto item: a[st]) {
    q.push({item.se * 1ll, item.fi});
  }
  for (int i = 0; i  n - 1; i++) {
    // connected graph, no need to worry empty
    while (dijk_dis[cnt][q.top().se] != inf) q.pop();
    pli hd = q.top();
    dijk_dis[cnt][hd.se] = hd.fi;
    for (auto item: a[hd.se]) {
      q.push({hd.fi + item.se, item.fi});
    }
  }
  cnt++;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin  n  m;
  vectorEdge e(m);
  for (int i = 0; i  m; i++) {
    cin  e[i].fr  e[i].to  e[i].len;
    a[e[i].fr].pb({e[i].to, e[i].len});
    a[e[i].to].pb({e[i].fr, e[i].len});
  }
  DSU dsu(n);
  for (int i = 0; i  m; i++) {
    dsu.add(e[i].fr, e[i].to, i);
  }
  for (auto item: dsu.st) {
    dijkstra(item);
  }
  for (int i = 1; i = n; i++) {
    a[i].clear();
  }
  for (int i = 0; i  m; i++) {
    if (!use[i]) continue;
    a[e[i].fr].pb({e[i].to, e[i].len});
    a[e[i].to].pb({e[i].fr, e[i].len});
  }
  dfs(1, 0, 0);
  for (int i = 1; i  maxd; i++) {
    for (int j = 1; j = n; j++) {
      fa[i][j] = fa[i - 1][fa[i - 1][j]];
    }
  }
  int q;
  cin  q;
  while (q--) {
    int x, y;
    cin  x  y;
    ll ans = dis[x] + dis[y] - dis[lca(x, y)] * 2;
    for (int i = 0; i  cnt; i++) {
      ll tmp = dijk_dis[i][x] + dijk_dis[i][y];
      ans = min(ans, tmp);
    }
    cout  ans  endl;
  }
  return 0;
}

 

最新回复(0)
/jishuH17JSKMCdfaNxAq5V2VVVS9b2_2FYsMX0v2wK5YVCFIns_3D4858277
8 简首页