You are given a weighed undirected connected graph, consisting of nn vertices and mm edges.

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 ;
}

最新文章

  1. linux下的audit服务
  2. 阿里云maven加速和docker加速
  3. Android SurfaceView
  4. Solr搜索服务架构图
  5. smarty3缓存设置
  6. BZOJ4196 软件包管理器
  7. PHP学习(前言)
  8. 销量预测和用户行为的分析--基于ERP的交易数据
  9. 2017蓝桥杯省赛C/C++B(补题中)
  10. 容器化现有ASP.NET MVC 5应用
  11. 《剑指offer》二叉树中和为某一值的路径
  12. java 基础01
  13. Windows环境下实现Consul服务注册和服务发现
  14. mysql三级连查,左连
  15. 程序打jar包
  16. noip2014无线网络发射器选址
  17. BZOJ.3489.A simple rmq problem(主席树 Heap)
  18. 检查 NaN 数据值 (C/C++/Python 实现)
  19. ctime, atime与mtime释疑
  20. PHP编码技巧

热门文章

  1. C#泛型链表Demo
  2. Zuul 2 : The Netflix Journey to Asynchronous, Non-Blocking Systems--转
  3. 关键字&amp;标识符
  4. 学习参考《Python数据分析与挖掘实战(张良均等)》中文PDF+源代码
  5. 【Linux探索之旅】第四部分第三课:文件传输,潇洒同步
  6. 思科2960trunk vlan配置及路由IP配置
  7. Java Swing设置主窗体位置居中方法
  8. Supermap 组合单值专题图与标签专题图演示样例
  9. Cocos2d-x怎样控制动作速度
  10. 手动连接数据库(jdbc)