1 #include <iostream>  2 #include <algorithm>  3 #include <cstring>  4 #include <string>  5 #include <cstdio>  6 #include <cmath>  7 #include <queue>  8 #include <map>  9 #include <set> 10  11 #define eps 1e-5 12 #define MAXN 55555 13 #define MAXM 111111 14 #define INF 1000000000 15 using namespace std; 16 int n, m, q; 17 struct edge 18 { 19     int v, next, w; 20 }es[MAXM]; 21 int head[MAXN], e; 22 int ide,tmpdfn; 23 int f[2 * MAXN], id[MAXN], used[MAXN], pos[MAXN], dis[MAXN]; 24 int mi[2 * MAXN][18]; 25  26 void init() 27 { 28     memset(head, -1, sizeof(head)); 29     e = 0; 30     ide = tmpdfn = 0; 31     memset(used, 0, sizeof(used)); 32     dis[1] = 0; 33 } 34  35 void add(int u, int v, int w) 36 { 37     es[e].v = v; 38     es[e].w = w; 39     es[e].next = head[u]; 40     head[u] = e++; 41 } 42 void dfs(int u) 43 { 44     used[u] = 1; 45     int tmp = ++tmpdfn; 46     f[++ide] = tmp; 47     id[tmp] = u; 48     pos[u] = ide; 49     for(int i = head[u]; i != -1; i = es[i].next) 50     { 51         int v = es[i].v; 52         if(!used[v]) 53         { 54             dis[v] = dis[u] + es[i].w; 55             dfs(v); 56             f[++ide] = tmp; 57         } 58     } 59      60 } 61 void rmqinit(int n, int *w) 62 { 63     for(int i = 1; i <= n; i++) mi[i][0] = w[i]; 64     int m = (int)(log(n * 1.0) / log(2.0)); 65     for(int i = 1; i <= m; i++) 66         for(int j = 1; j <= n; j++) 67         { 68             mi[j][i] = mi[j][i - 1]; 69             if(j + (1 << (i - 1)) <= n) mi[j][i] = min(mi[j][i], mi[j + (1 << (i - 1))][i - 1]); 70         } 71 } 72  73 int rmqmin(int l,int r) 74 { 75     int m = (int)(log((r - l + 1) * 1.0) / log(2.0)); 76     return min(mi[l][m] , mi[r - (1 << m) + 1][m]); 77 } 78  79 int LCA(int l, int r) 80 { 81     if(pos[l] > pos[r]) swap(l, r); 82     int ans = rmqmin(pos[l], pos[r]); 83     return id[ans]; 84 } 85 int main() 86 { 87    // freopen("/Users/apple/Desktop/题/POJ 1986_1/POJ 1986_1/in","r",stdin); 88     scanf("%d%d", &n, &m); 89     int u, v, w, l, r; 90     init(); 91     while(m--) 92     { 93         scanf("%d%d%d%*s", &u, &v, &w); 94         add(u, v, w); 95         add(v, u, w); 96     } 97     dfs(1); 98     rmqinit(ide, f); 99     scanf("%d", &q);100     while(q--)101     {102         scanf("%d%d", &l, &r);103         printf("%d\n", dis[l] + dis[r] - 2 * dis[LCA(l, r)]);104     }105     return 0;106 }