You should answer qq queries, the ii-th query is to find the shortest distance between vertices uiui and vivi.
Input
The first line contains two integers n and m (1≤n,m≤105,m−n≤20) — the number of vertices and edges in the graph.
Next m lines contain the edges: the i-th edge is a triple of integers vi,ui,di (1≤ui,vi≤n,1≤di≤109,ui≠vi). This triple means that there is an edge between vertices ui and vi of weight di. It is guaranteed that graph contains no self-loops and multiple edges.
The next line contains a single integer q (1≤q≤105)— the number of queries.
Each of the next qq lines contains two integers uiui and vi (1≤ui,vi≤n)vi (1≤ui,vi≤n) — descriptions of the queries.
Pay attention to the restriction m−n ≤ 20
Output
Print q lines.
The i-th line should contain the answer to the i-th query — the shortest distance between vertices ui and vi.
解题思路：
题目非常良心地强调了m-n<=20
建一颗dfs树，对于未加入树的边两端跑Dij
询问只要枚举未入树边更新即可。
代码：
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long lnt;
struct pnt{
int hd;
int dp;
int no;
int fa[];
lnt dis;
lnt tds;
bool vis;
bool cop;
bool friend operator < (pnt x,pnt y)
{
return x.dis>y.dis;
}
}p[];
struct ent{
int twd;
int lst;
lnt vls;
}e[];
std::priority_queue<pnt>Q;
int n,m;
int q;
int cnt;
int sct;
lnt dist[][];
int sta[];
void ade(int f,int t,lnt v)
{
cnt++;
e[cnt].twd=t;
e[cnt].vls=v;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
void Dij(int x)
{
if(p[x].cop)
return ;
p[x].cop=true;
sta[++sct]=x;
for(int i=;i<=n;i++)
{
p[i].dis=0x3f3f3f3f3f3f3f3fll;
p[i].no=i;
p[i].vis=false;
}
p[x].dis=;
while(!Q.empty())
Q.pop();
Q.push(p[x]);
while(!Q.empty())
{
x=Q.top().no;
Q.pop();
if(p[x].vis)
continue;
p[x].vis=true;
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].dis>p[x].dis+e[i].vls)
{
p[to].dis=p[x].dis+e[i].vls;
Q.push(p[to]);
}
}
}
for(int i=;i<=n;i++)
dist[sct][i]=p[i].dis;
return ;
}
void dfs(int x,int f)
{
p[x].fa[]=f;
p[x].dp=p[f].dp+;
for(int i=;i<=;i++)
p[x].fa[i]=p[p[x].fa[i-]].fa[i-];
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(to==f)
continue;
if(p[to].tds)
{
Dij(x);
Dij(to);
}else{
p[to].tds=p[x].tds+e[i].vls;
dfs(to,x);
}
}
}
int Lca(int x,int y)
{
if(p[x].dp<p[y].dp)
std::swap(x,y);
for(int i=;i>=;i--)
if(p[p[x].fa[i]].dp>=p[y].dp)
x=p[x].fa[i];
if(x==y)
return x;
for(int i=;i>=;i--)
if(p[x].fa[i]!=p[y].fa[i])
{
x=p[x].fa[i];
y=p[y].fa[i];
}
return p[x].fa[];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
ade(a,b,c);
ade(b,a,c);
}
p[].tds=;
dfs(,);
scanf("%d",&q);
while(q--)
{
int x,y;
scanf("%d%d",&x,&y);
int f=Lca(x,y);
lnt ans=p[x].tds+p[y].tds-*p[f].tds;
for(int i=;i<=sct;i++)
ans=std::min(ans,dist[i][x]+dist[i][y]);
printf("%I64d\n",ans);
}
return ;
}