当前位置： 移动技术网 > IT编程>开发语言>C/C++ > HDU 2874 LCA转RMQ+并查集

HDU 2874 LCA转RMQ+并查集

2019年01月12日  | 移动技术网IT编程  | 我要评论

华莉丝 迪里耶,自然之道的意思,qinwenjiejie

题意：问两个城市是否相连，不相连输出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

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网