點擊打開鏈接
題意：問兩個城市是否相連，不相連輸出Not connected，否則輸出兩個城市間的最短距離
思路：用並查集判斷兩個城市的連通性，如果聯通則做法和LCA一樣，但是注意的一點是地圖不連通的話，我們要將所有點都建起來，就要加一個模擬的點，將所有圖串起來，很好處理的，看一下就會了
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=10010;
struct edge{
int to,cost;
edge(int a,int b){to=a;cost=b;}
};
vectorG[maxn];
int dp[maxn*2][20],L[maxn*2],E[maxn*2],dis[maxn],H[maxn],f[maxn];
bool vis[maxn];
int n,k;
void dfs(int t,int deep){
k++;E[k]=t;L[k]=deep;H[t]=k;
for(unsigned int i=0;iri) swap(le,ri);
int kk=0;
while((1<<(kk+1))<=ri-le+1) kk++;
if(L[dp[le][kk]]
