给一个N个点M条边的连通无向图，满足每条边最多属于一个环，有Q组询问，每次询问两点之间的最短路径。

输入的第一行包含三个整数，分别表示N和M和Q 下接M行，每行三个整数v，u，w表示一条无向边v-u，长度为w 最后Q行，每行两个整数v，u表示一组询问

输出Q行，每行一个整数表示询问的答案

对于100%的数据，N<=10000，Q<=10000

  1 #include <cstdio>  2 #include <cstring>  3   4 inline int nextChar(void)  5 {  6     static const int siz = 1 << 20;  7       8     static char buf[siz];  9     static char *hd = buf + siz; 10     static char *tl = buf + siz; 11      12     if (hd == tl) 13         fread(hd = buf, 1, siz, stdin); 14          15     return int(*hd++); 16 } 17  18 inline int nextInt(void) 19 { 20     int r = 0, c = nextChar(); 21      22     for (; c < 48; c = nextChar()); 23     for (; c > 47; c = nextChar()) 24         r = r * 10 + c - ‘0‘; 25      26     return r; 27 } 28  29 template <class T> 30 inline T min(const T &a, const T &b) 31 { 32     return a < b ? a : b; 33 } 34  35 template <class T> 36 inline T abs(const T &x) 37 { 38     return x < 0 ? -x : x; 39 } 40  41 const int mxn = 500005; 42 const int inf = 0x3f3f3f3f; 43  44 int n, m, q; 45  46 int tot; 47 int hd[mxn]; 48 int to[mxn]; 49 int vl[mxn]; 50 int nt[mxn]; 51  52 inline void add(int x, int y, int w) 53 { 54     nt[tot] = hd[x]; 55     to[tot] = y; 56     vl[tot] = w; 57     hd[x] = tot++; 58 } 59  60 int dis[mxn]; 61 int que[mxn]; 62 int vis[mxn]; 63  64 inline void spfa(void) 65 { 66     memset(vis,   0, sizeof vis); 67     memset(dis, inf, sizeof dis); 68      69     int lt = 0, rt = 0; 70      71     que[rt++] = 1; 72     vis[1] = 1; 73     dis[1] = 0; 74      75     while (lt != rt) 76     { 77         int u = que[lt++], v; 78  79         if (lt > mxn)lt = 0; 80          81         vis[u] = 0; 82          83         for (int i = hd[u]; ~i; i = nt[i]) 84             if (v = to[i], dis[v] > dis[u] + vl[i]) 85             { 86                 dis[v] = dis[u] + vl[i]; 87                  88                 if (!vis[v]) 89                 { 90                     vis[que[rt++] = v] = 1; 91  92                     if (rt > mxn)rt = 0; 93                 } 94             } 95     } 96 } 97  98 struct data 99 {100     int u, v, w;101     102     inline data(void) {};103     inline data(int a, int b, int c)104         : u(a), v(b), w(c) {};105 }stk[mxn]; int top;106 107 int tim;108 int dfn[mxn];109 int low[mxn];110 111 int cnt;112 int cir[mxn];113 int len[mxn];114 int bel[mxn];115 int fat[mxn][25];116 117 inline void addcir(int u, int v)118 {119     ++cnt;120     121     while (u != stk[top].u && v != stk[top].v)122     {123         int x = stk[top].u, y = stk[top].v, w = stk[top].w;124         125         if (x != u)bel[x] = cnt, fat[x][0] = u;126         if (y != u)bel[y] = cnt, fat[y][0] = u;127         128         len[cnt] += w, cir[x] = cir[y] + w;129         130         --top;131     }132     133     {134         int x = stk[top].u, y = stk[top].v, w = stk[top].w;135         136         len[cnt] += w, cir[x] = cir[y] + w;137         138         fat[y][0] = x;139         140         --top;141     }142 }143 144 void tarjan(int u, int f)145 {146     dfn[u] = low[u] = ++tim;147     148     for (int i = hd[u], v; ~i; i = nt[i])149         if ((v = to[i]) != f)150         {151             if (!dfn[v])152             {153                 stk[++top] = data(u, v, vl[i]), tarjan(v, u);154                 155                 if (low[v] < low[u])low[u] = low[v];156                 157                 if (low[v] >= dfn[u])addcir(u, v);158             }159             else if (dfn[v] < low[u])160                 low[u] = dfn[v], stk[++top] = data(u, v, vl[i]);    161         }162 }163 164 int dep[mxn];165 166 void build(int u)167 {168     for (int i = hd[u]; ~i; i = nt[i])169         dep[to[i]] = dep[u] + 1, build(to[i]);170 }171 172 inline void prework(void)173 {174     spfa();175     176     tarjan(1, 0);177     178     for (int i = 1; i <= 20; ++i)179         for (int j = 1; j <= n; ++j)180             fat[j][i] = fat[fat[j][i - 1]][i - 1];181     182     memset(hd, -1, sizeof hd), tot = 0;183     184     for (int i = 2; i <= n; ++i)185         add(fat[i][0], i, 0);186     187     dep[1] = 1, build(1);188 }189 190 inline int getLCA(int a, int b, int &x, int &y)191 {192     if (dep[a] < dep[b])193         a ^= b ^= a ^= b;194     195     int ret = dis[a] + dis[b];196     197     for (int i = 20; ~i; --i)198         if (dep[fat[a][i]] >= dep[b])199             a = fat[a][i];200     201     if (a == b)202         return x = y = a, ret - dis[a] * 2;203     204     for (int i = 20; ~i; --i)205         if (fat[a][i] != fat[b][i])206             a = fat[a][i],207             b = fat[b][i];208     209     return x = a, y = b, ret - dis[fat[a][0]] * 2;210 }211 212 signed main(void)213 {214     n = nextInt();215     m = nextInt();216     q = nextInt();217     218     memset(hd, -1, sizeof(hd)), tot = 0;219     220     for (int i = 1; i <= m; ++i)221     {222         int x = nextInt();223         int y = nextInt();224         int w = nextInt();225         226         add(x, y, w);227         add(y, x, w);228     }229     230     prework();231     232     for (int i = 1, x, y; i <= q; ++i)233     {234         int a = nextInt();235         int b = nextInt();236         237         int ans = getLCA(a, b, x, y);238         239         if (bel[x] && bel[x] == bel[y])240         {241             ans = dis[a] + dis[b] - dis[x] - dis[y];242             243             int len1 = abs(cir[x] - cir[y]);244             int len2 = len[bel[x]] - len1;245             246             ans += min(len1, len2);247         }248         249         printf("%d\n", ans);250     }251 }