这道题思路比较有意思，第一次做完全没想到点子上。。。

---

看到题目第一反应是一道最短路裸题，但是数据范围1e5说明完全不可能。

这个时候可以观察到题目给出了一个很有意思的条件，就是说边最多比点多20。

这有什么用呢？

那么我们大胆猜想，可否将整个图划分为21条边（连接最多42个点）和一颗树？（极限情况）

如果这样的话，对于任意的两个节点uv，它们之间的最短路只有两种情况：

1. 这两个点都在树上。所以说最短路必然是u->lca(u,v)->v。

2. 不是上面那种情况。这个时候肯定会有连到外面那21个边。我们暴力枚举一下就可以了。

到这里思路就完全出来了，我们先把不属于树的点挑出来，对每一个都跑一下最短路。

然后对于每一组询问判断一下属于哪一种情况就可以了。

---

AC代码如下：

37657ms 67712kb

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;namespace StandardIO{    template
         
          inline void read(T &x){ x=0;T f=1;char c=getchar(); for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1; for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0'; x*=f; } template
          
           inline void write(T x){ if(x<0)putchar('-'),x*=-1; if(x>=10)write(x/10); putchar(x%10+'0'); }}using namespace StandardIO;namespace Solve{ #define int long long const int N=100100; const int INF=2147483647; int n,m,p; int cnt; int head[N]; struct node{ int to,val,next; }edge[N<<1]; template
           
            inline void add(T a,T b,T c){ edge[++cnt].to=b,edge[cnt].val=c,edge[cnt].next=head[a],head[a]=cnt; } struct qnode{ int key,val; bool operator < (qnode x)const{ return val>x.val; } }; int top; int vis[N],fa[N][23],dist[N],dep[N],q[N]; int dis[50][N]; inline void dfs(int now,int father){ vis[now]=1,fa[now][0]=father; for(register int i=head[now];i;i=edge[i].next){ int to=edge[i].to; if(to==father)continue; if(vis[to])q[++top]=now,q[++top]=to; else{ dep[to]=dep[now]+1,dist[to]=dist[now]+edge[i].val; dfs(to,now); } } } template
            
             inline T lca(T x,T y){ if(dep[x]
             
              =0;--i){ if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; } if(x==y)return x; for(register int i=19;i>=0;--i){ if(fa[x][i]!=fa[y][i]){ x=fa[x][i],y=fa[y][i]; } } return fa[x][0]; } inline void dijkstra(int now){ memset(dis[now],63,sizeof(dis[now])); memset(vis,0,sizeof(vis)); priority_queue
              
               Q; dis[now][q[now]]=0; Q.push((qnode){q[now],0}); while(!Q.empty()){ int tmp=Q.top().key;Q.pop(); if(vis[tmp])continue; vis[tmp]=1; for(register int i=head[tmp];i;i=edge[i].next){ int to=edge[i].to; if(!vis[to]&&dis[now][tmp]+edge[i].val