#include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <bitset> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define maxn 40005 struct node { int x,l; }; vector<node> V[maxn]; int E[maxn * 2], D[maxn * 2], first[maxn]; int vis[maxn], dist[maxn], n, m, top = 1, root[maxn], st; int dp[30][maxn * 2]; void () { top = 1; memset(root, 0, sizeof(root)); memset(vis, 0, sizeof(vis)); scanf("%d %d", &n,&m); for (int i = 1; i <= n; i++) { V[i].clear(); } int a, b,c; node tmp; for (int i = 0; i < m; i++) { char d; scanf(" %d %d %d %c", &a, &b,&c,&d); tmp.x = b; tmp.l=c; V[a].push_back(tmp); tmp.x = a; V[b].push_back(tmp); root[b] = 1; } for (int i = 1; i <= n; i++) if (root[i] == 0) { st = i; break; } dist[st]=0; } void dfs(int u, int dep) { vis[u] = 1, E[top] = u, D[top] = dep, first[u] = top++; for (int i = 0; i < V[u].size(); i++) if (!vis[V[u][i].x]) { int v = V[u][i].x; dist[v]=dist[u]+V[u][i].l; dfs(v, dep + 1); E[top] = u, D[top++] = dep; } } void ST(int num) { for (int i = 1; i <= num; i++) { dp[0][i] = i; } for (int i = 1; i <= log2(num); i++) for (int j = 1; j <= num; j++) if (j + (1 << i) - 1 <= num) { int a = dp[i - 1][j], b = dp[i - 1][j + (1 << i >> 1)]; if (D[a] < D[b]) { dp[i][j] = a; } else { dp[i][j] = b; } } } int RMQ(int x, int y) { int k = (int) log2(y - x + 1.0); int a = dp[k][x], b = dp[k][y - (1 << k) + 1]; if (D[a] < D[b]) { return a; } return b; } int main () { init(); dfs(st, 0); ST(top); int x, y; int k; cin>>k; while(k--) { scanf("%d%d", &x, &y); int a = first[x], b = first[y]; if (a > b) { swap(a, b); } int pos = RMQ(a, b); printf("%dn",dist[x]+dist[y]-2*dist[E[pos]]); } return 0; }
|
近期评论