1 #include <cstdio>  2 #include <cmath>  3 #include <algorithm>  4 #include <queue>  5 #include <cstring>  6 using namespace std;  7 #define INF 2000000000  8 #define V 100008  9 #define E 300008 10 #define clr(x,v) memset(x,v,sizeof(x)) 11 int cnt,n,m,q; 12 int ui[100],vi[100],wi[100],f[100100],l[100100][20],dep[100100],s[100100]; 13 int id[V],rk[108],num,dist[108][V]; 14 struct edge{ 15     int u,w; 16 }; 17 vector <edge> e[100100]; 18 struct line{ 19     int u,v,w,nt; 20 }eg[E]; 21 int lt[V],sum; 22 void add(int u,int v,int w){ 23     eg[++sum]=(line){u,v,w,lt[u]}; 24     lt[u]=sum; 25 } 26 int father(int x) 27 { 28     if(f[x]==x)return x; 29     f[x]=father(f[x]); 30     return f[x]; 31 } 32  33 void dfs(int x,int fa,int sum) 34 { 35     l[x][0]=fa; 36     s[x]=sum; 37     dep[x]=dep[fa]+1; 38     for(int i = 0;i < e[x].size();i++) 39     { 40         int u=e[x][i].u; 41         if(u!=fa) 42         { 43             dfs(u,x,sum+e[x][i].w); 44         } 45     } 46 } 47  48 int lca(int a,int b) 49 { 50     if(dep[a]<dep[b])swap(a,b); 51     int d=dep[a]-dep[b]; 52     for(int i = 0;i <= 18;i++) 53         if(d&(1<<i))a=l[a][i]; 54     if(a==b)return a; 55     for(int i = 18;i >= 0;i--) 56         if(l[a][i]!=l[b][i]) 57         { 58             a=l[a][i]; 59             b=l[b][i]; 60         } 61     return l[a][0]; 62 } 63 int dis(int x,int y){ 64     int p=lca(x,y); 65     return s[x]+s[y]-s[p]*2; 66 } 67  68 int d[V],pd[V]; 69 queue <int> Q; 70 void spfa(int s){ 71     for (int i=1;i<=n;i++){ 72         d[i]=INF; 73         pd[i]=0; 74     } 75     d[s]=0; pd[s]=1; Q.push(s); 76     while (!Q.empty()){ 77         int u=Q.front(); 78         Q.pop(); 79         for (int i=lt[u];i;i=eg[i].nt){ 80             int v=eg[i].v; 81             if (d[u]+eg[i].w<d[v]){ 82                 d[v]=d[u]+eg[i].w; 83                 if (!pd[v]){ 84                     pd[v]=1; 85                     Q.push(v); 86                 } 87             } 88         } 89         pd[u]=0; 90     } 91     for (int i=1;i<=n;i++) dist[id[s]][i]=d[i]; 92 } 93 void work() 94 { 95     for(int i = 1;i <= 18;i++) 96         for(int j = 1;j <= n;j++) 97             l[j][i]=l[l[j][i-1]][i-1]; 98     for (int i=1;i<=num;i++) spfa(rk[i]); 99     while (q--){100         int u,v;101         scanf("%d%d",&u,&v);       102         int ans=dis(u,v);103         for (int i=1;i<=num;i++)104             ans=min(ans,dist[i][u]+dist[i][v]); 105         printf("%d\n",ans);106     }107 }108 int main()109 {110     int t,cas=0;111     scanf("%d",&t);112     while(t--)113     {114         clr(lt,0); sum=0;115         cnt=0; num=0;116         clr(id,0);117         printf("Case %d:\n",++cas);118         scanf("%d%d%d",&n,&m,&q);119         for(int i = 1;i <= n;i++)e[i].clear();120         for(int i = 1;i <= n;i++)f[i]=i;121         for(int i = 1;i <= m;i++)122         {123             int u,v,w;124             scanf("%d%d%d",&u,&v,&w);125             add(u,v,w);126             add(v,u,w);127             if(father(u)!=father(v))128             {129                 f[father(u)]=father(v);130                 e[u].push_back((edge){v,w});131                 e[v].push_back((edge){u,w});132             }133             else134             {135                 cnt++;136                 ui[cnt]=u;137                 vi[cnt]=v;138                 wi[cnt]=w;139                 if (!id[u]){140                     id[u]=++num;141                     rk[num]=u;142                 }143                 if (!id[v]){144                     id[v]=++num;145                     rk[num]=v;146                 }147             }148         }149         dfs(1,0,0);150         work();151     }152     return 0;153 }