JZTXT

最短路

发布时间 2023-07-19 18:48:17作者: jingyu0929

最短路

  • \(Floyd\) 算法
  • \(Dijkstra\) 算法
  • \(SPFA\) 算法

 这些算法都很熟悉，基本的就不多说了。

T1 1993 小K的农场

 差分约束，跑一遍 \(spfa\) 判断有没有负环就可以了。

struct node{
	int v,w;
};

int n,m;
vector<node> e[N];
int dis[N];
bool flag[N];
int cnt[N];

bool spfa() {
	queue<int> q;
	memset(dis,0x3f,sizeof dis);
	q.push(0);
	dis[0] = 0;
	while (q.size()) {
		auto u = q.front();
		q.pop();
		flag[u] = false;
		
		for (auto it : e[u]) {
			int v = it.v,w = it.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!flag[v]) {
					cnt[v] ++;
					if (cnt[v] > n) return false;
					flag[v] = true;
					q.push(v);
				}
			}
		}
	}
	return true;
}

int main(){
	n = fr(),m = fr();
	for (int i = 1; i <= n; i ++) {
		e[0].push_back({i,0});
	}
	int type,a,b,w;
	while (m --) {
		type = fr();
		if (type == 1) {
			a = fr(),b = fr(),w = fr();
			e[a].push_back({b,-w});
		} else if (type == 2) {
			a = fr(),b = fr(),w = fr();
			e[b].push_back({a,w});
		} else {
			a = fr(),b = fr();
			e[a].push_back({b,0});
			e[b].push_back({a,0});
		}
	}
	if (spfa()) yj;
	else wj;
	return 0;
}

2757 等差子序列

 是昨天的题，哈希。

 因为他说了这是一个连续的排列，所以我们一个个遍历，如果遍历到了就将当前位置标记为 \(1\) ，只有当这个标记数组一直是回文串的时候，他才没有等差数列。

 举个例子，如果序列是 \(3,2,1\) ，那么这个标记数组的变化就是 \(001 -> 011 -> 111\) ，可以发现第一个和第二个不是回文串，所以这里是有等差数列的。

 然后判断回文串的话就用线段树结合哈希来判断是不是回文串，维护的话就维护正着和倒着两个哈希值。

struct node{
	lwl pre,suf;
}tr[N << 2];

int n;
int w[N];
lwl poww[N];

void init(){
	poww[0] = 1;
	for (int i = 1; i < N; i ++) {
		poww[i] = poww[i - 1] * p % mod;
	}
}

void pushup(int idx,int lenl,int lenr) {
	tr[idx].pre = tr[ir].pre + tr[il].pre * poww[lenr];
	tr[idx].pre %= mod;
	tr[idx].suf = tr[ir].suf * poww[lenl] + tr[il].suf;
	tr[idx].suf %= mod;
}

void modify(int L,int R,int l,int r,int idx) {
	if (L == l && R == r) {
		tr[idx].pre = 1;
		tr[idx].suf = 1;
		return ;
	}
	int mid = (L + R) >> 1;
	if (mid >= l) modify(L,mid,l,r,il);
	if (mid < r) modify(mid + 1,R,l,r,ir);
	pushup(idx,mid - L + 1,R - mid);
}

lwl query(int L,int R,int l,int r,int idx,int type) {
	if (L > R || l > r) return 0;
	if (L >= l && R <= r) {
		if (type == 1) return tr[idx].pre;
		else return tr[idx].suf;
	}
	int mid = (L + R) >> 1;
	if (r <= mid) return query(L,mid,l,r,il,type);
	if (l > mid) return query(mid + 1,R,l,r,ir,type);
	lwl ll = query(L,mid,l,r,il,type); 
	lwl rr = query(mid + 1,R,l,r,ir,type);
	lwl ans;
	if (type == 1) ans = ll * poww[min(r,R) - mid] + rr;
	else ans = rr * poww[mid - (max(L,l)) + 1] + ll;
	return ans % mod;
}

int main(){
	int T = fr();
	init();
	while (T --) {
		n = fr();
		for (int i = 1; i <= n; i ++) {
			w[i] = fr();
		}
		bool flag = false;
		memset(tr,0,sizeof tr);
		for (int i = 1; i <= n; i ++) {
			int len = min(w[i] - 1,n - w[i]);
			lwl a = query(1,n,w[i] - len,w[i] - 1,1,1);
			lwl b = query(1,n,w[i] + 1,w[i] + len,1,2);
			if (a != b) {
				flag =  true;
				break;
			}
			modify(1,n,w[i],w[i],1);
		}
		if (flag) yj;
		else wj;
	}
	return 0;
}

还有就是，我宣布哈希是玄学算法！！！！

T3 5304 旅行者

 这个题是最短路加上二进制，搞两个源点，一个作为起点一个作为终点。然后对于每一个特殊的点，把二进制的每一位都遍历一遍，如果 \(j \&(1 << i)\) 的话，就先把他和起点连一条长度为 \(0\) 的边，然后其余点和终点连一条长度为 \(0\) 的边，然后从起点到终点跑一遍 \(dij\) 最短路，然后再反过来跑一遍，在其中取最小值就是答案。

 因为两个点之间的最短距离那么这两个点的编号一定是不一样的，这样就可以把所有两个点之间的距离最小值给求出来，但是不知道是哪两个点。（好像再开一个数组是可以的（？））

 然后就是这一题不要忘记开 \(lwl\) 了。

struct node{
	int v;
	lwl w;
};

int n,m,k;
int S,T;
vector<node> e[N],temp[N];
int w[N];
lwl dis[N];
bool flag[N];

lwl dij() {
	memset(dis,0x3f,sizeof dis);
	memset(flag,0,sizeof flag);
	priority_queue<pii,vector<pii>,greater<pii> > q;
	dis[S] = 0;
	q.push({dis[S],S});
	while (q.size()) {
		auto t = q.top();
		q.pop();
		
		int u = t.se;
		if (flag[u]) continue;
		
		for (auto it : e[u]) {
			int v = it.v;
			lwl val = it.w;
			if (dis[v] > dis[u] + val) {
				dis[v] = dis[u] + val;
				q.push({dis[v],v});
			}
		}
		flag[u] = true;
	}
	return dis[T];
}

int main(){
	int TT = fr();
	while (TT --) {
		n = fr(),m = fr(),k = fr();
		for (int i = 1; i <= n + 2; i ++) {
			temp[i].clear();
		}
		int a,b,ww;
		while (m --) {
			a = fr(),b = fr(), ww = fr();
			temp[a].push_back({b,ww});
		}
		for (int i = 1; i <= k; i ++) w[i] = fr();
		S = n + 1,T = n + 2;
		lwl ans = linf;
		for (int i = 0; (1 << i) <= k; i ++) {
			for (int j = 1; j <= n + 2; j ++) {
				e[j] = temp[j];
			}
			for (int j = 1; j <= k; j ++) {
				if (j & (1 << i)) {
					e[S].push_back({w[j],0});
				} else {
					e[w[j]].push_back({T,0});
				}
			}
			ans = min(ans,dij());
			for (int j = 1; j <= n + 2; j ++) {
				e[j] = temp[j];
			}
			for (int j = 1; j <= k; j ++) {
				if (j & (1 << i)) {
					e[w[j]].push_back({T,0});
				} else {
					e[S].push_back({w[j],0});
				}
			}
			ans = min(ans,dij());
		}
		fw(ans);
		ch;
	}
	return 0;
}

练习

 今天是 \(OI\) 赛制，但是其中三题洛谷上面都有原题，所以我的评价是 \(OI\) 但不完全 \(OI\) 。前面三题比较简单，就是第一题一开始无解的时候要输出 “No important cities.”，然后我一开始写的时候没有看到还有一个英文句号，还是 \(Tak1na\) 说了之后才发现的

 第四题一开始正解写挂了，然后比赛结束之后找了 \(Richard\_H\) 的 \(dij\) 写法，过了。然后去找老师问正解怎么改，改了几个地方之后才 \(AC\)

A.重要的城市

 用 \(Floyd\) 算最短路的过程中把每两个点之间的最短路的数量都算出来，如果 \(cnt[i][j] = cnt[i][k] \times cnt[k][j]\) 就说明 \(i,j\) 之间的最短路一定要经过 \(k\) 点，然后这样处理之后就可以求了。

int n,m;
lwl cnt[N][N];
int dis[N][N];

int main(){
	memset(dis,0x3f,sizeof dis);
	n = fr(),m = fr();
	for (int i = 1; i <= n; i ++)
		dis[i][i] = 0;
	for (int i = 1; i <= m; i ++) {
		int a = fr(),b = fr(),c = fr();
		dis[a][b] = dis[b][a] = c;
		cnt[a][b] = cnt[b][a] = 1;
	}
	for (int k = 1; k <= n; k ++) {
		for (int i = 1; i <= n; i ++) {
			if (i == k) continue;
			for (int j = 1; j <= n; j ++) {
				if (j == k || j == i) continue;
				if (dis[i][j] > dis[i][k] + dis[k][j]) {
					dis[i][j] = dis[i][k] + dis[k][j];
					cnt[i][j] = cnt[i][k] * cnt[k][j];
				} else if (dis[i][j] == dis[i][k] + dis[k][j]) {
					cnt[i][j] += cnt[i][k] * cnt[k][j];
				}
			}
		}
	}
	bool st = false;
	for (int k = 1; k <= n; k ++) {
		bool flag = false;
		for (int i = 1; i <= n; i ++) {
			if (i == k) continue;
			for (int j = 1; j <= n; j ++) {
				if (j == k || j == i) continue;
				if (cnt[i][j] == cnt[i][k] * cnt[k][j] && dis[i][j] == dis[i][k] + dis[k][j]) {
					fw(k),kg;
					st = true,flag = true;
					break;
				}
			}
			if (flag) break;
		}
	}
	if (!st) wj;
	return 0;
}

B.新年好

 这个是 \(ACwing\) 上面以前做过的原题，就是先把这六个点的单源最短路都求出来，然后用 \(nextpermutation\) 或者 \(dfs\) 枚举一下每一个走过的顺序就可以了。感觉挺暴力的。

 然后这一题根据 \(Tak1na\) 所说，如果用 \(spfa\) 会 \(T\) 掉，然后用 \(SLF\) 优化在洛谷也有一个点过不了。但是信友队这里 \(spfa\) 可以冒过去，数据就是水啦。

struct node{
	int v,w;
};

int n,m;
int a[7];
vector<node> e[N];
int dis[7][N];
int siz[N];
bool flag[N];

void dij(int st,int dis[]) {
	memset(dis,0x3f,sizeof siz);
	memset(flag,0,sizeof flag);
	priority_queue<pii,vector<pii>,greater<pii> > q;
	dis[st] = 0;
	q.push({dis[st],st});
	while (q.size()) {
		auto t = q.top();
		q.pop();
		
		int u = t.se;
		if (flag[u]) continue;
		
		for (auto it : e[u]) {
			int v = it.v,w = it.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!flag[v])
					q.push({dis[v],v});
			}
		}
		flag[u] = true;
	}
}

int main(){
	n = fr(),m = fr();
	for (int i = 2; i <= 6; i ++) {
		a[i] = fr();
	}
	a[1] = 1;
	for (int i = 1; i <= m; i ++) {
		int a = fr(),b = fr(),w = fr();
		e[a].push_back({b,w});
		e[b].push_back({a,w});
	}
	for (int i = 1; i <= 6; i ++) {
		dij(a[i],dis[i]);
	}
	int h[7] = {0,1,2,3,4,5,6};
	int ans = inf;
	do{
		int res = dis[1][a[h[2]]];
		for (int i = 2; i <= 5; i ++) {
			res += dis[h[i]][a[h[i + 1]]];
		}
		ans = min(ans,res);
	} while (next_permutation(h + 2,h + 7));
	fw(ans);
	ch;
	return 0;
}

C.飞行路线

 分层图，把每一个航班都弄成好几个点，然后连边的时候就每次都连多一点，然后最后算的时候就取一个 \(min\) 就可以了。理论上来说如果直接用 \(dis[T + n * k]\) 也是可以的，但是我没有试，反正次数也不多，跑一跑算了。

 这个要注意的一点就是如果 \(k = 10\) 的话其实是有 \(11 * n\) 个点的，所以开数组的时候不能只开十倍，不然会 \(RE\) 一个点（在洛谷上交的时候 \(RE\) 了）

struct node {
	int v,w;
};

int n,m,k;
int S,T;
vector<node> e[N];
lwl dis[N];
bool flag[N];

void dij() {
	memset(dis,0x3f,sizeof dis);
	memset(flag,0,sizeof flag);
	priority_queue<pii,vector<pii>,greater<pii> > q;
	
	dis[S] = 0;
	q.push({dis[S],S});
	while (q.size()) {
		auto t = q.top();
		q.pop();
		
		int u = t.se;
		if (flag[u]) continue;
		
		for (auto it : e[u]) {
			int v = it.v,w = it.w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!flag[v]) q.push({dis[v],v});
			}
		}
		
		flag[u] = true;
	}
}

int main(){
	n = fr(), m = fr(), k = fr();
	S = fr(), T = fr();
	while (m --) {
		int a = fr(), b = fr(), w = fr();
		e[a].push_back({b,w});
		e[b].push_back({a,w});
		
		for (int i = 1; i <= k; i ++) {
			a += n,b += n;
			e[a].push_back({b,w});
			e[b].push_back({a,w});
			e[a - n].push_back({b,0});
			e[b - n].push_back({a,0});
		}
	}
	dij();
	lwl ans = linf;
	for (int i = 0; i <= k; i ++) {
		ans = min(ans,dis[T + i * n]);
	}
	fw(ans);
	return 0;
}

D.护送

 这个题一开始正解写挂了，气死了。

 就是用了 \(Floyd\) 的性质：用于松弛的点只有之前遍历过的 \(k\) 点。所以我们就把所有点按照 \(c_i\) 排一个序，保证每一条当前的最短路的 \(c_i\) 最大值要么是在起点和终点处，要么就是在 \(k\) 点。

 然后要注意的就是内层的两个循环都要从 \(1 - n\) 全部跑一遍，要不然有些情况没有考虑到。还有就是这里的 \(temp[i][i]\) 和 \(dis[i][i]\) 要初始化为 \(0\) ，要不然就会痛失就十分。

int n,m;
int dis[N][N];
int temp[N][N];
int w[N];
int id[N];

bool cmp(int a,int b) {
	return w[a] < w[b];
}

int main(){
	memset(temp,0x3f,sizeof temp);
	memset(dis,0x3f,sizeof dis);
	n = fr(),m = fr();
	for (int i = 1; i <= n; i ++) {
		w[i] = fr();
	}
	for (int i = 1; i <= m; i ++) {
		int a = fr(),b = fr(),c = fr();
		temp[a][b] = temp[b][a] = min(temp[a][b],c);
	}
	for (int i = 1; i <= n; i ++) {
		id[i] = i;
	}
	for (int i = 1; i <= n; i ++) {
		dis[i][i] = 0;
		temp[i][i] = 0;
	}
	sort(id + 1,id + 1 + n,cmp);
	for (int k = 1; k <= n; k ++) {
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				if (j == i) continue;
				if (temp[id[i]][id[j]] > temp[id[i]][id[k]] + temp[id[k]][id[j]])
					temp[id[i]][id[j]] = temp[id[i]][id[k]] + temp[id[k]][id[j]];
			}
		}
		for (int i = 1; i <= n; i ++) {
			for (int j = 1; j <= n; j ++) {
				dis[id[i]][id[j]] = min(dis[id[i]][id[j]],temp[id[i]][id[k]] + temp[id[k]][id[j]] + w[id[max(i,max(j,k))]]);
			}
		}
	}
	int Q = fr();
	while (Q --) {
		int a = fr(),b = fr();
		fw(dis[a][b]);
		ch;
	}
	return 0;
}

E.种树

 差分约束，然后每一个 \(dis\) 都维护到那里的前缀和就可以。然后可以把题目给的几个等式都转化为不等式，然后差分约束跑一遍最长路直接输出 \(dis[n]\) 就可以了。

 然后这里的 \(dis\) 要记得初始化为 \(-inf\) ，不然就会寄掉 \(20\) 分（不是我寄的，但是 \(Richard\_H\)寄了）

struct node{
	int v,w;
};

int n,m;
int w[N];
int dis[N];
bool flag[N];
vector<node> e[N];

void spfa() {
	memset(dis,-0x3f,sizeof dis);
	memset(flag,0,sizeof flag);
	queue<int> q;
	q.push(0);
	dis[0] = 0;
	while (q.size()) {
		auto u = q.front();
		q.pop();
		
		flag[u] = false;
		
		for (auto it : e[u]) {
			int v = it.v,w = it.w;
			if (dis[v] < dis[u] + w) {
				dis[v] = dis[u] + w;
				if (!flag[v]) {
					q.push(v);
					flag[v] = true;
				}
			}
		}
	}
}

int main(){
	n = fr(),m = fr();
	for (int i = 1; i <= n; i ++) {
		w[i] = fr();
		e[i].push_back({i - 1,-w[i]});
		e[i - 1].push_back({i,0});
	}
	while (m --) {
		int l = fr(),r = fr(),w = fr();
		e[l - 1].push_back({r,w});
	}
	spfa();
	fw(dis[n]);
	return 0;
}