Description
給定一個有 N 個點，M條邊的圖，有 Q 個詢問，每次詢問兩個點之間的最短距離。
對于100%的資料，2<=N<=10000，N−1<=M<=12000，Q=10000。
時間限制 100ms 。
啊，我不會做！
嗯，當然，還有一點忘說了，隻有三類資料：
- M=N-1（樹）30%
- M=N（環套外向樹）50%
- 每條邊僅在一個簡單環中（仙人掌）10%
什麼，你問30%+50%+10%=90%!=100%，其實剩下那10%是送的。
Analysis
這是本蒟蒻的第一道仙人掌。
顯然，仙人掌就包括了前兩種情況，但是出題人毒瘤，不僅出這種業界毒瘤，仙人掌還隻給10分。
這裡有一種把仙人掌變成樹的方法，感謝alan大神百度搜尋提供的資料，搜尋技術高超。像我這種蒟蒻搜到的全都是
真是美麗的仙人掌啊！
好吧，廢話不說了。
上面的方法形象地解釋就是這樣：
定義環頂為一個環裡dfn最小的點。
如圖，設紅色的點是環頂。
若兩個點在同一個環中，如下圖兩個藍色的點
那他們的距離顯然是從環的兩邊走的較小的那一個。
是以我們要求出每個環的大小 size ，以及從一邊走的距離 dis ，這樣兩個在同一個環裡的點的距離就是 min(dis,size−dis) 。
當然，我們變成樹之後，設詢問的兩個點為 x,y,lca(x,y)=lca ， u,v 表示lca的兩個兒子。這樣子說不清，如下圖：
若 u,v 在不在同一環中，則直接 dis[x]+dis[y]−2∗dis[lca] ，當然， dis 要 sp(b)fa 搞出來。
否則，x，y不在同一個環中，是以直接用dis[x]-dis[u]+dis[y]-dis[v]+(u到v環上的距離)即可。
Code
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
#define efo(i,v) for(int i=last[v];i;i=next[i])
using namespace std;
const int N=10010,M=N*5;
int tot,n,m,num,st[M],to[M],next[M],wei[M],last[N];
int now,dep[N],dis[N],di[N],from[N],dfn[N],val[N],lyd[N],f[N][15];
bool bz[M],vis[M];
queue<int> q;
void link(int u,int v,int w)
{
st[++tot]=u,to[tot]=v,wei[tot]=w,next[tot]=last[u],last[u]=tot;
}
void spfa()
{
q.push(1);
bz[1]=1;
memset(dis,60,sizeof(dis));
dis[1]=0;
while(!q.empty())
{
int u=q.front();q.pop();
bz[u]=0;
efo(i,u)
{
int v=to[i];
if(dis[u]+wei[i]<dis[v])
{
dis[v]=dis[u]+wei[i];
if(!bz[v])
{
bz[v]=1;
q.push(v);
}
}
}
}
}
void rt(int i,int t)
{
++num;
while(1)
{
int v=to[i];
if(to[i]!=t && st[i]!=t)
{
bz[i]=bz[i^1]=1;
link(v,t,0),link(t,v,0);
}
val[num]+=wei[i];
if(st[i]!=t) lyd[st[i]]=num;
if(st[i]==t) break;
i=from[st[i]];
}
}
void dfs1(int v,int fr)
{
dfn[v]=++now;
efo(i,v)
{
int u=to[i];
if(u==fr || bz[i]) continue;
if(!dfn[u])
{
from[u]=i,di[u]=di[v]+wei[i];
dfs1(u,v);
}
else
if(dfn[u]<dfn[v]) rt(i,u);
}
}
void dfs2(int v,int fr,int k)
{
vis[v]=1;
dep[v]=k,f[v][0]=fr;
efo(i,v)
{
int u=to[i];
if(bz[i] || u==fr || vis[u]) continue;
dfs2(u,v,k+1);
}
}
int getlca(int &u,int &v)
{
if(dep[u]>dep[v]) swap(u,v);
fd(i,int(log2(dep[v])),0)
if(dep[f[v][i]]>=dep[u]) v=f[v][i];
if(u==v) return u;
fd(i,int(log2(dep[v])),0)
if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
return f[u][0];
}
int main()
{
int _,x,y,u,v,w;
scanf("%d %d %d",&n,&m,&_);
tot=1;
fo(i,1,m)
{
scanf("%d %d %d",&u,&v,&w);
link(u,v,w),link(v,u,w);
}
spfa();
dfs1(1,1);
dfs2(1,1,1);
fo(j,1,int(log2(n)))
fo(i,1,n) f[i][j]=f[f[i][j-1]][j-1];
while(_--)
{
scanf("%d %d",&x,&y);
int lca=getlca(u=x,v=y);
if(lyd[u] && lyd[v] && lyd[u]==lyd[v])
{
int k=abs(di[u]-di[v]);
k=min(k,val[lyd[u]]-k);
printf("%d\n",dis[x]+dis[y]-dis[u]-dis[v]+k);
}
else
printf("%d\n",dis[x]+dis[y]-2*dis[lca]);
}
return 0;
}