洛谷 P8312 [COCI2021-2022#4] Autobus题目题解代码实现

116 阅读 0 评论 77 点赞

我是靠谱客的博主复杂篮球，这篇文章主要介绍洛谷 P8312 [COCI2021-2022#4] Autobus题目题解代码实现，现在分享给大家，希望可以做个参考。

PS：如果读过题了可以跳过题目描述直接到题解部分
提交链接：洛谷 P8312 [COCI2021-2022#4] Autobus

题目

题目描述

在一个国家里有 $n$ 座城市。这些城市由 $m$ 条公交线路连接，其中第 $i$ 条线路从城市 $a_i$ 出发，到 $b_i$ 停止，路程中耗时 $t_i$ 分钟。

Ema 喜欢旅行，但她并不喜欢在公交线路之间换乘。在旅行过程中，她希望最多只需坐 $k$ 个不同的公交线路。

Ema 想知道，从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间是多少（最多坐 $k$ 个不同的公交线路）。

输入格式

第一行包含两个整数 $n, m$ ，分别表示城市的数量和公交车线路的数量。

接下来 $m$ 行，第 $i + 1$ 包含三个整数 $a_i,b_i,t_i$ ，分别表示第 $i$ 条公交车线路的起点、终点和从起点到终点所需的时间。

接下来一行包含两个整数 $k, q$ ，最大坐的不同公交线路的个数和问题题的个数。

接下来 $q$ 行，第 $m + j + 3$ 行包含两个整数 $c_j,d_j$ ，表示询问从城市 $c_j$ 到城市 $d_j$ 的最短旅行时间。

输出格式

输出包含 $q$ 行，第 $i$ 行包含一个整数，表示从城市 $c_i$ 到城市 $d_i$ 的最短旅行时间。

样例 #1

样例输入 #1

复制代码

样例输出 #1

复制代码

样例 #2

样例输入 #2

复制代码

样例输出 #2

复制代码

样例 #3

样例输入 #3

复制代码

样例输出 #3

复制代码

提示

【样例解释】

每个样例中的答案都已经标记在图中。

【数据规模与约定】

本题采用子任务捆绑测试。

Subtask 1（15 pts）： $k \leq n \leq 7$ 。
Subtask 2（15 pts）： $k \leq 3$ 。
Subtask 3（25 pts）： $k \leq n$ 。
Subtask 4（15 pts）：没有额外限制。

对于 $100%$ 的数据， $m,t_ile 10^6,1le a_i,b_i,c_j,d_jle n,1le kle10^9,1le q le n^2$ 。

【提示与说明】

本题分值按 COCI 原题设置，满分 $70$ 。

题目译自 COCI2021-2022 CONTEST #4 T2 Autobus。

题解

30pts

floyd+次数

$O(n^5)$
在floyd中循环更新的次数。

70pts

次数+floyd

$O(n^4)$
因为每次更新一定比上一次更优，所以我们先循环更新的次数再循环floyd。（注意连边的时候就是第一次更新了）

代码实现

30pts

复制代码

//洛谷 P8312 [COCI2021-2022#4] Autobus
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int x=0x3f3f3f3f;
int n,m;
int u,v,t;
int r[75][75][75];
int k,q;
int a[75][75];

void in(int &x){
	int nt;
	x=0;
	while(!isdigit(nt=getchar()));
	x=nt^'0';
	while(isdigit(nt=getchar())){
		x=(x<<3)+(x<<1)+(nt^'0');
	}
}

void pre(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			for(int l=1;l<=n;++l){
				for(int o=1;o<=k;++o){
					for(int p=1;p<=k-o;++p){
						r[j][l][o+p]=min(r[j][l][o+p],r[j][i][o]+r[i][l][p]);
						if(r[j][l][o+p]<a[j][l]){
							a[j][l]=r[j][l][o+p];
						}
					}
				}
			}
		}
	}
}

int main(){
	register int i;
	in(n),in(m);
	memset(r,x,sizeof(r));
	memset(a,x,sizeof(a));
	for(i=1;i<=n;++i){
		a[i][i]=r[i][i][1]=0;
	}
	for(i=1;i<=m;++i){
		in(u),in(v),in(t);
		if(u==v){
			continue;
		}
		a[u][v]=r[u][v][1]=min(r[u][v][1],t);
	}
	in(k),in(q);
	k=min(k,n);
	pre();
	for(i=1;i<=q;++i){
		in(u),in(v);
		if(a[u][v]==x){
			printf("-1n");
		}
		else{
			printf("%dn",a[u][v]);
		}
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//洛谷 P8312 [COCI2021-2022#4] Autobus
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int x=0x3f3f3f3f;
int n,m;
int u,v,t;
int r[75][75][75];
int k,q;
int a[75][75];

void in(int &x){
	int nt;
	x=0;
	while(!isdigit(nt=getchar()));
	x=nt^'0';
	while(isdigit(nt=getchar())){
		x=(x<<3)+(x<<1)+(nt^'0');
	}
}

void pre(){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			for(int l=1;l<=n;++l){
				for(int o=1;o<=k;++o){
					for(int p=1;p<=k-o;++p){
						r[j][l][o+p]=min(r[j][l][o+p],r[j][i][o]+r[i][l][p]);
						if(r[j][l][o+p]<a[j][l]){
							a[j][l]=r[j][l][o+p];
						}
					}
				}
			}
		}
	}
}

int main(){
	register int i;
	in(n),in(m);
	memset(r,x,sizeof(r));
	memset(a,x,sizeof(a));
	for(i=1;i<=n;++i){
		a[i][i]=r[i][i][1]=0;
	}
	for(i=1;i<=m;++i){
		in(u),in(v),in(t);
		if(u==v){
			continue;
		}
		a[u][v]=r[u][v][1]=min(r[u][v][1],t);
	}
	in(k),in(q);
	k=min(k,n);
	pre();
	for(i=1;i<=q;++i){
		in(u),in(v);
		if(a[u][v]==x){
			printf("-1n");
		}
		else{
			printf("%dn",a[u][v]);
		}
	}
	return 0;
}

70pts

复制代码

void in(int &x){
	int nt;
	x=0;
	while(!isdigit(nt=getchar()));
	x=nt^'0';
	while(isdigit(nt=getchar())){
		x=(x<<3)+(x<<1)+(nt^'0');
	}
}

void pre(){
	for(int o=1;o<=k-1;++o){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				b[i][j]=a[i][j];
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				for(int l=1;l<=n;++l){
					b[j][l]=min(b[j][l],a[j][i]+r[i][l]);
				}
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				a[i][j]=b[i][j];
			}
		}
	}
}

int main(){
	register int i;
	in(n),in(m);
	memset(r,x,sizeof(r));
	memset(a,x,sizeof(a));
	for(i=1;i<=n;++i){
		a[i][i]=r[i][i]=0;
	}
	for(i=1;i<=m;++i){
		in(u),in(v),in(t);
		if(u==v){
			continue;
		}
		a[u][v]=r[u][v]=min(r[u][v],t);
	}
	in(k),in(q);
	k=min(k,n);
	pre();
	for(i=1;i<=q;++i){
		in(u),in(v);
		if(a[u][v]==x){
			printf("-1n");
		}
		else{
			printf("%dn",a[u][v]);
		}
	}
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//洛谷 P8312 [COCI2021-2022#4] Autobus
#pragma GCC optimize(3)
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int x=0x3f3f3f3f;
int n,m;
int u,v,t;
int r[75][75];
int k,q;
int a[75][75];
int b[75][75];

void in(int &x){
	int nt;
	x=0;
	while(!isdigit(nt=getchar()));
	x=nt^'0';
	while(isdigit(nt=getchar())){
		x=(x<<3)+(x<<1)+(nt^'0');
	}
}

void pre(){
	for(int o=1;o<=k-1;++o){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				b[i][j]=a[i][j];
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				for(int l=1;l<=n;++l){
					b[j][l]=min(b[j][l],a[j][i]+r[i][l]);
				}
			}
		}
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				a[i][j]=b[i][j];
			}
		}
	}
}

int main(){
	register int i;
	in(n),in(m);
	memset(r,x,sizeof(r));
	memset(a,x,sizeof(a));
	for(i=1;i<=n;++i){
		a[i][i]=r[i][i]=0;
	}
	for(i=1;i<=m;++i){
		in(u),in(v),in(t);
		if(u==v){
			continue;
		}
		a[u][v]=r[u][v]=min(r[u][v],t);
	}
	in(k),in(q);
	k=min(k,n);
	pre();
	for(i=1;i<=q;++i){
		in(u),in(v);
		if(a[u][v]==x){
			printf("-1n");
		}
		else{
			printf("%dn",a[u][v]);
		}
	}
	return 0;
}

最后

以上就是复杂篮球最近收集整理的关于洛谷 P8312 [COCI2021-2022#4] Autobus题目题解代码实现的全部内容，更多相关洛谷内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。

本文分类：图论
浏览次数：116 次浏览
发布日期：2023-12-20 23:15:09
本文链接：https://www.kaopuke.com/article/k-p-k_13_u_23_o_2_f1_13_z_22_y.html

洛谷 P8312 [COCI2021-2022#4] Autobus题目题解代码实现

题目

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

提示

题解

30pts

floyd+次数

70pts

次数+floyd

代码实现

30pts

70pts

最后

评论列表共有 0 条评论

发表评论取消回复

洛谷 P8312 [COCI2021-2022#4] Autobus题目题解代码实现

题目

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

样例 #3

样例输入 #3

样例输出 #3

提示

题解

30pts

floyd+次数

70pts

次数+floyd

代码实现

30pts

70pts

最后

相关文章

评论列表共有 0 条评论

发表评论 取消回复

微信扫一扫：分享

发表评论取消回复