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

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

【题解】

先跑一遍$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;
}
99employee.com 说:
2023年4月18日 17:23

To compensate for rising commodity prices, Dearness Allowance is added to ounces salary, and this is combined with basic salary and HRA to increase employee net worth. The allowance is a varying amount that is always 99employee.com increasing, and it differs for state, central, and PSU employees.For security and analysis purposes, the posting IP address is used.

jnanabhumiap.in 说:
2024年1月05日 20:20

JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. jnanabhumiap.in To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us.


登录 *


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