After World War X, a lot of cities have been seriously damaged, and we need to rebuild those cities. However, some materials needed can only be produced in certain places. So we need to transport these materials from city to city. For most of roads had been totally destroyed during the war, there might be no path between two cities, no circle exists as well.
Now, your task comes. After giving you the condition of the roads, we want to know if there exists a path between any two cities. If the answer is yes, output the shortest path between them.
Input
Input consists of multiple problem instances.For each instance, first line contains three integers n, m and c, 2<=n<=10000, 0<=m<10000, 1<=c<=1000000. n represents the number of cities numbered from 1 to n. Following m lines, each line has three integers i, j and k, represent a road between city i and city j, with length k. Last c lines, two integers i, j each line, indicates a query of city i and city j.
Output
For each problem instance, one line for each query. If no path between two cities, output “Not connected”, otherwise output the length of the shortest path between them.
Sample Input
5 3 2
1 3 2
2 4 3
5 2 3
1 4
4 5
Sample Output
Not connected
6
Hint
Huge input, scanf recommended.
这题是典型的LCA问题，就是是求树上任意两点的距离，只不过这个可以不是只有一棵树，而是森林，所以需要设一些虚边（虚边的权值为0）把这些森林合并成一颗树，判断两个点链不连通，用并查即可，关于如何实现LCA，这次又其他的方式来实现，可以把LCA转化为RMQ问题，然后最RMQ的实现则采用st算法。具体思路可参考链接
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<vector>
#include<cmath>
#define N 10005
using namespace std;
int n,m,c;
int total;
int pre[N];
int findd(int x)
{
return pre[x]==x?x:pre[x]=findd(pre[x]);
}
vector<int> graph[N];
struct node
{
int x1,x2,w;
}edge[N];
int k;
int fa[N];
int p;
int index1;
int E[N*2],L[N*2],H[N];
int dis[N];
void addEdge(int x,int y,int w)
{
edge[k].x1=x;
edge[k].x2=y;
edge[k].w=w;
graph[x].push_back(k);
graph[y].push_back(k);
k++;
}
void dfs(int x,int fa,int cur)//一次dfs求出E、L、dis数组
{
E[index1]=x;
L[index1]=cur;
index1++;
for(int i=0;i<graph[x].size();i++)
{
int ind=graph[x][i];
int v=edge[ind].x1==x?edge[ind].x2:edge[ind].x1;
if(v==fa)
continue;
dis[v]=dis[x]+edge[ind].w;
dfs(v,x,cur+1);
E[index1]=x;
L[index1]=cur;
index1++;
}
}
void init(int x)
{
for(int i=1;i<=x;i++)
graph[i].clear();
for(int i=1;i<=x;i++)
pre[i]=i;
memset(dis,0,sizeof(dis));
k=0;
p=0;
index1=1;
}
int dp[N*2][16];
void rmq()//RMQ
{
int cnt=ceil(log(total*1.0)/log(2.0));
for(int i=1;i<=total;i++)
dp[i][0]=i;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=total;j++)
{
dp[j][i]=dp[j][i-1];
if(j+(1<<(i-1))<=total)
if(L[dp[j][i-1]]>L[dp[j + (1<<(i - 1))][i - 1]])
dp[j][i]=dp[j + (1 << (i - 1))][i - 1];
}
}
int indMin(int l,int r)//返回坐标
{
int cnt =(int)(log((r - l + 1)*1.0)/log(2.0));
if(L[dp[l][cnt]]>L[dp[r - (1 << cnt) + 1][cnt]])
return dp[r - (1 << cnt) + 1][cnt];
else
return dp[l][cnt];
}
int query(int p1,int p2)
{
int l=H[p1];
int r=H[p2];
if(l>r)
{
int temp=l;
l=r;
r=temp;
}
int ans=E[indMin(l,r)];//ans即为两点的LCA
return dis[p1]+dis[p2]-2*dis[ans];
}
int main()
{
int x,y,w;
//cout<<pow(2,14);
while(scanf("%d%d%d",&n,&m,&c)==3)
{
init(n);
total=2*n-1;
while(m--)
{
scanf("%d%d%d",&x,&y,&w);
addEdge(x,y,w);
int xx=findd(x);
int yy=findd(y);
if(xx!=yy)
pre[xx]=yy;
}
for(int i=1;i<=n;i++)
if(pre[i]==i)
fa[p++]=i;//把所有的森林的root放入fa数组
for(int i=1;i<p;i++)//
addEdge(fa[i-1],fa[i],0);//然后把root与root之间连虚边
dfs(1,-1,0);
memset(H,-1,sizeof(H));
for(int i=1;i<=total;i++)
if(H[E[i]]==-1)
H[E[i]]=i;
rmq();
/*for(int i=1;i<=total;i++) { for(int j=0;j<=4;j++) cout<<dp[i][j]<<":"<<L[dp[i][j]]<<" "; cout<<endl; }*/
while(c--)
{
scanf("%d%d",&x,&y);
int xx=findd(x);
int yy=findd(y);
if(xx!=yy)//先判断连通
printf("Not connected\n");
else
printf("%d\n",query(x,y));
}
}
return 0;
}