程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU2874 Connections between cities 最近公共祖先+離線

HDU2874 Connections between cities 最近公共祖先+離線

編輯：C++入門知識

給了你n個村莊把，然後m條路徑，q個詢問，問你兩個點之間的最短距離

分析：由於按照題意來說本圖是沒有環的，所以求a,b的最近公共祖先到他們的各自的距離之和就是那個他們的最短路啦，用的是tarjan來做的，我的方法定義了一個dis數組來隨時記錄路徑的長度，其它大神各有自己的神奇之法

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include

#define ll long long

#define LL __int64

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector > G;
//typedef pair P;
//vector > ::iterator iter;
//
//mapmp;
//map::iterator p;

const int N = 10000 + 5;
const int MAXN = 2000000 + 5;

int pre[N];
int head[N],qhead[N];
int dis[N];
bool vis[N];
int tot,qtot;

typedef struct Node {
	int from,nex,to;
	int lca;
};

Node edge[N * 2],qedge[MAXN];

void clear() {
	memset(dis,0,sizeof(dis));
	memset(vis,false,sizeof(vis));
	memset(head,-1,sizeof(head));
	memset(qhead,-1,sizeof(qhead));
	for(int i=0;i<=N;i++)
		pre[i] = i;
	tot = qtot = 0;
}


void addedge(int u,int v,int w) {
	edge[tot].nex = head[u];
	edge[tot].to = v;
	edge[tot].lca = w;
	head[u] = tot++;
}

void addqedge(int u,int v) {
	qedge[qtot].nex = qhead[u];
	qedge[qtot].from = u;
	qedge[qtot].to = v;
	qedge[qtot].lca = -1;
	qhead[u] = qtot++;
}

int find(int x) {
	if(pre[x] != x)return find(pre[x]);
	return pre[x];
}

void LCA(int u) {
	pre[u] = u;
	vis[u] = true;
	for(int i=head[u];i!=-1;i=edge[i].nex) {
		if(!vis[edge[i].to]) {
			dis[edge[i].to] = dis[u] + edge[i].lca;
			LCA(edge[i].to);
			pre[edge[i].to] = u;
		}
	}
	for(int i=qhead[u];i!=-1;i=qedge[i].nex) {
		if(vis[qedge[i].to]) {
			qedge[i].lca = dis[qedge[i].to] - dis[find(qedge[i].to)] + dis[u] - dis[find(qedge[i].to)];
			qedge[i ^ 1].lca = qedge[i].lca;
		}
	}
}

int main() {
	int n,m,q;
	while(scanf("%d %d %d",&n,&m,&q) == 3) {
		clear();
		while(m--) {
			int u,v,w;
			scanf("%d %d %d",&u,&v,&w);
			addedge(u,v,w);
			addedge(v,u,w);
		}
		for(int i=0;i