BZOJ2725 [Violet 6]故乡的梦 【dijkstra+线段树】

tonyfang posted @ 2016年8月18日 19:23 in BZOJ with tags c++ OI , 894 阅读

【题解】

先跑一遍$S-T$的最短路,记录下路径

预处理出来$dS_{i}$表示$S$到$i$的最短路,$frS_{i}$表示$S$到$i$的最短路上,第一个离开$S-T$最短路的点,同理$dT_{i}$表示$i$到$T$的最短路,$frT_{i}$表示$i$到$T$最短路上,第一个进入$S-T$最短路的点。

然后我们枚举每条边$(x,y)$,那么如果要经过$(x,y)$,那么最短路就是$dS_{x} + w_{x,y} + dT_{y}$,然后我们就可以用一棵线段树来维护这个玩意儿。

 

# include <stdio.h>
# include <algorithm>
# include <string.h>
# include <stdlib.h>
# include <map>
# include <queue>
# define MP make_pair
# define fi first
# define se second

using namespace std;

typedef long long ll;

#define pii pair<int,int>
#define pil pair<ll,int>
int n, m;
int head[200010], to[400010], next[400010], w[400010], tot=0;
ll dS[200010], dT[200010];
int S, T, from[400010], frS[400010], frT[400010];
bool vis[200010];
int route[200010], rtn = 0, rtpos[200010];
const ll INF = 10000000000000000LL;
map< pil, int> bh;
int U[200010], V[200010]; 
ll W[200010];
int Qn, Qs, Qt;

inline ll MIN(ll x, ll y) {
	return x<y?x:y;
}

inline void add(int u, int v, int tw) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	w[tot]=tw;
} 

priority_queue<pii, vector< pil >, greater< pil > > Q;

inline void dijkstra() {
	while(!Q.empty()) Q.pop();
	int start = S;
	for (int i=1; i<=n; ++i) dS[i] = INF, vis[i] = 0;
	dS[start] = 0;
	Q.push(MP(0, start));
	while(!Q.empty()) {
		pil s = Q.top(); Q.pop();
		if(vis[s.se]) continue;
		vis[s.se] = 1;
		for (int i=head[s.se]; i; i=next[i]) 
			if(!vis[to[i]] && dS[s.se] + w[i] < dS[to[i]]) {
				dS[to[i]] = dS[s.se] + w[i];
				from[to[i]] = s.se;
				Q.push(MP(dS[to[i]], to[i]));
			}
	}
} 

inline void dijkstra1() {
	while(!Q.empty()) Q.pop();
	int start = S;
	for (int i=1; i<=n; ++i) dS[i] = INF, vis[i] = 0;
	dS[start] = 0;
	Q.push(MP(0, start));
	while(!Q.empty()) {
		pil s = Q.top(); Q.pop();
		if(vis[s.se]) continue;
		if(rtpos[s.se]) frS[s.se] = s.se;
		vis[s.se] = 1;
		for (int i=head[s.se]; i; i=next[i]) 
			if(!vis[to[i]] && dS[s.se] + w[i] < dS[to[i]]) {
				dS[to[i]] = dS[s.se] + w[i];
				frS[to[i]] = frS[s.se];
				Q.push(MP(dS[to[i]], to[i]));
			}
	}
} 

inline void dijkstra2() {
	while(!Q.empty()) Q.pop();
	int start = T;
	for (int i=1; i<=n; ++i) dT[i] = INF, vis[i] = 0;
	dT[start] = 0;
	Q.push(MP(0, start));
	while(!Q.empty()) {
		pil s = Q.top(); Q.pop();
		if(vis[s.se]) continue;
		if(rtpos[s.se]) frT[s.se] = s.se;
		vis[s.se] = 1;
		for (int i=head[s.se]; i; i=next[i]) 
			if(!vis[to[i]] && dT[s.se] + w[i] < dT[to[i]]) {
				dT[to[i]] = dT[s.se] + w[i];
				frT[to[i]] = frT[s.se];
				Q.push(MP(dT[to[i]], to[i]));
			}
	}
} 

//=====================================================//

int lc[1200010], rc[1200010];
ll we[1200010];
inline void build(int x, int l, int r) {
	lc[x] = l, rc[x]= r; we[x]=INF;
	if(l == r) return; 
	int mid=l+r>>1;
	build(x<<1, l, mid);
	build(x<<1|1, mid+1, r);
}

inline void change(int x, int l, int r, long long val) {
	int L=lc[x], R=rc[x];
	if(l<=L && R<=r) {
//		printf("insert?! %I64d\n", val);
		we[x] = MIN(we[x], val); 
		return;
	}
	int mid=L+R>>1;
	if(r<=mid) change(x<<1, l, r, val);
	else if(l>mid) change(x<<1|1, l, r, val);
	else {
		change(x<<1, l, mid, val);
		change(x<<1|1, mid+1, r, val);
	}
}

inline ll query(int x, int pos) {
	int L=lc[x], R=rc[x];
	if(L==R) 
		return we[x];
	int mid=L+R>>1;
	if(pos<=mid) return MIN(we[x], query(x<<1, pos));
	else return MIN(we[x], query(x<<1|1, pos)); 
}

//=====================================================//


int main() {
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; ++i) {
		scanf("%d%d%d", &U[i], &V[i], &W[i]);
		if(U[i]>V[i]) swap(U[i], V[i]);
		add(U[i], V[i], W[i]);
		add(V[i], U[i], W[i]);
	}
	scanf("%d%d", &S, &T);
	dijkstra();
	for (int i=T; i!=S; i=from[i])
		route[++rtn] = i;
	route[++rtn] = S;
	
//	for (int i=1; i<=rtn; ++i) printf("%d --> ", route[i]);
//	puts("");

//	for (int i=rtn; i>=1; --i) printf("%d ", route[i]);
//	printf("%d\n", dS[T]);	
	for (int i=1; i<=rtn; ++i)	
		rtpos[route[i]] = rtn-i+1;
	
	for (int i=2; i<=rtn; ++i) {
		int posx, posy;
		posx = min(route[i], route[i-1]);
		posy = route[i]+route[i-1]-posx;
		bh[MP(posx, posy)] = rtn-i+1;
//		printf("relabel: x=%d, y=%d. rei=%d\n", posx, posy, rtn-i+1);	
	}
	
	dijkstra1();
	dijkstra2();
	
//	printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");	
	
//	for (int i=1; i<=n; ++i) printf("%d ", frS[i]);
//	printf("\n");
//	for (int i=1; i<=n; ++i) printf("%d ", frT[i]);
//	printf("\n"); 	
//	for (int i=1; i<=n; ++i) printf("%I64d ", dS[i]);
//	printf("\n");
//	for (int i=1; i<=n; ++i) printf("%I64d ", dT[i]);
//	printf("\n"); 
//	printf("RTPOS\n");
//	for (int i=1; i<=n; ++i) printf("%d ", rtpos[i]);
	

//	printf("@@@@@@@@@@@@@@@@@@@@@@@@@@@\n");	
	
	
	build(1, 1, rtn-1);
	for (int i=1; i<=m; ++i) {
		if(bh.find(MP(U[i], V[i])) != bh.end()) continue;
		int left = rtpos[frS[U[i]]], right = rtpos[frT[V[i]]] - 1;
//		printf("   U[i] = %d, V[i] = %d\n", U[i], V[i]);
//		printf("checking left=%d right=%d\n", left, right);
		if(left <= right) {
//			printf("checking ok!!! we = %I64d\n", dS[U[i]] + dT[V[i]] + W[i]);
			change(1, left, right, dS[U[i]] + dT[V[i]] + W[i]);
		}
		swap(U[i], V[i]);
		left = rtpos[frS[U[i]]], right = rtpos[frT[V[i]]] - 1;
//		printf("   U[i] = %d, V[i] = %d\n", U[i], V[i]);
//		printf("checking left=%d right=%d\n", left, right);
		if(left <= right) {
//			printf("checking ok!!! we = %I64d\n", dS[U[i]] + dT[V[i]] + W[i]);
			change(1, left, right, dS[U[i]] + dT[V[i]] + W[i]);
		}
	}

	
//	for (int i=1; i<=rtn*4; ++i) 
//		printf("i=%d, leftchild = %d, rightchild = %d, value = %I64d\n", i, lc[i], rc[i], we[i]);
 
	
	scanf("%d", &Qn);
	while(Qn--) {
		ll ans;
		scanf("%d%d", &Qs, &Qt);
		if(Qs > Qt) swap(Qs, Qt);
		if(bh.find(MP(Qs, Qt)) == bh.end())
			ans = dS[T];
		else {
			int pos = bh[MP(Qs, Qt)];
			ans = query(1, pos);
		}
		if(ans == INF) puts("Infinity");
		else printf("%lld\n", ans);
	}
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter