1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <queue> 5 using namespace std; 6 #define N 100010 7 struct Edge { 8     int v, nxt, w; 9     Edge () {}10     Edge (int v, int nxt, int w) : v(v), nxt(nxt), w(w) {}11 } edge[N];12 int dp[N][30], dep[N], dis[N], fa[N], head[N], tot, n;13 14 void Add(int u, int v, int w) {15     edge[tot] = Edge(v, head[u], w); head[u] = tot++;16     edge[tot] = Edge(u, head[v], w); head[v] = tot++;17 }18 19 void DFS(int u) {20     dp[u][0] = fa[u];21     for(int i = 1; i <= 20; i++) // 转移22         dp[u][i] = dp[dp[u][i-1]][i-1];23     for(int i = head[u]; ~i; i = edge[i].nxt) {24         int v = edge[i].v;25         if(v == fa[u]) continue;26         fa[v] = u;27         dep[v] = dep[u] + 1;28         dis[v] = dis[u] + edge[i].w;29         DFS(v);30     }31 }32 33 int LCA(int x, int y) {34     if(dep[x] < dep[y]) swap(x, y); //设x为较深的点35     for(int i = 20; i >= 0; i--) // 让x跑到和y同一深度36         if(dep[dp[x][i]] >= dep[y]) x = dp[x][i];37     if(x == y) return x;38     for(int i = 20; i >= 0; i--) // x和y同时向上跑39         if(dp[x][i] != dp[y][i])40             x = dp[x][i], y = dp[y][i];41     return dp[x][0];42 }43 44 int main() {45     int m, q;46     while(~scanf("%d%d", &n, &m)) {47         memset(dp, 0, sizeof(dp));48         memset(dis, 0, sizeof(dis));49         memset(dep, 0, sizeof(dep));50         memset(head, -1, sizeof(head));51         tot = 0; char s[4];52         for(int i = 0; i < m; i++) {53             int u, v, w;54             scanf("%d%d%d%s", &u, &v, &w, s);55             Add(u, v, w);56         }57         fa[1] = 1; dis[1] = dep[1] = 0;58         DFS(1);59         scanf("%d", &q);60         while(q--) {61             int u, v;62             scanf("%d%d", &u, &v);63             printf("%d\n", dis[u] + dis[v] - dis[LCA(u, v)] * 2);64         }65     }66     return 0;67 }