【题目】跨栏题解
【题目】
题目描述
校运会快开始了，小花正在练习跨栏。 显然，对于运动员跳过几个矮栏是很容易的，但是高栏却很难。于是，小花非常关心路径上最高的栏的高度。
学校的训练场中有 N 个站台，分别标记为 1,2,3,…,N。所有站台之间有 M 条单向路径，第 i 条路经是从站台 Si 开始，到站台 Ei，其中最高的栏的高度为 Hi。无论如何跑，小花都要跨栏。
小花有 T 个训练任务要完成。第 i个任务包含两个数字 Ai 和 Bi，表示小花必须从站台 Ai 跑到站台 Bi，可以路过别的站台。小花想找一条路径从站台 Ai 到站台 Bi，使路径上最高的栏的高度最小。 你的任务就是写一个程序，计算出路径上最高的栏的高度的最小值。
输入格式
第一行：三个空格隔开的整数 N, M, T。
接下来 M 行：第 i 行包含三个空格隔开的整数 Si,Ei,Hi。
接下来 T行：第 i 行包含两个空格隔开的整数，表示任务 ii 的起始站台和目标站台 Ai,Bi。
输出格式
T 行：第 i 行为一个整数，表示任务 i路径上最高的栏的高度的最小值。如果无法到达，输出 -1。
样例 #1
样例输入 #15 6 3
1 2 12
3 2 8
1 3 5
2 5 3
3 4 4
2 4 8
3 4
1 2
5 1
样例输出 #14
8
-1
提示
对于 100%的数据1<=N<=300,1<=M<=250000,1<=Hi<=1000000,1<=T<=40000,1<=Ai,Bi<=N
【思路】
1.初始化：将a数组先设为无穷大，然后输入，建边
int n,m,l;
scanf("%d%d%d",&n,&m,&l);
memset(a,0x3f,sizeof(a));
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]=z;
}
2.使用floyd算法，因为N<=300，比较小，O（N^3）不会超时，而且明显是全局最短路
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}
}
}
注意：这个代码只是框架，还要在上面做些改动
因为题目说是求中间最大值，不是最短路，所以将a[i][k]+a[k][j]变成max(a[i][k],a[k][j]),就OK了
3.最后输出一下就行了，注意要判断-1
怎么判断呢？
因为我们最开始使用了memset(a,0x3f,sizeof(a)),所以判断一下a[i][j]是否为0x3f3f3f3f就行了
如果a[i][j]=0x3f3f3f3f的话：输出-1
否则：输出a[i][j]
for(int i=1;i<=l;i++){
int x,y;
cin>>x>>y;
if(a[x][y]==0x3f3f3f3f){
cout<<-1<<endl;
}
else{
cout<<a[x][y]<<endl;
}
}
【完整代码】
那么很容易就得到了完整代码了
#include<bits/stdc++.h>
using namespace std;
int a[305][305];
int main(){
int n,m,l;
scanf("%d%d%d",&n,&m,&l);
memset(a,0x3f,sizeof(a));
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
a[x][y]=z;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=min(a[i][j],max(a[i][k],a[k][j]));
}
}
}
for(int i=1;i<=l;i++){
int x,y;
cin>>x>>y;
if(a[x][y]==0x3f3f3f3f){
cout<<-1<<endl;
}
else{
cout<<a[x][y]<<endl;
}
}
return 0;
}
相关知识
ZUST 程序设计算法竞赛基础【1】题解报告
Hello world Python新手赛题解
[题目]某植物园引进了一种珍稀花卉.为了使其大量繁殖.并让游客尽早欣赏到该花.最适合进行( )A. 有性生殖 B. 孢子生殖C. 播种 D. 植物组织培养 题目和参考答案——青夏教育精英家教网——
花花公子男士冰丝无痕背心外穿薄款紧身健身运动跨栏吊带夏季潮白 49元（需用券）
题解 P5662 [CSP
【题解】樱花 （混合背包）
蓝桥杯算法提高VIP
园林化工中级理论知识题解.doc 全文免费在线看
NOIP模拟测试49·50「养花·折射·画作·施工·蔬菜·联盟」
切花题目答案解析,切花题目答案解析
网址: 【题目】跨栏题解 https://m.huajiangbk.com/newsview368501.html
| 上一篇: 校园花坛标语（八篇） |
下一篇: 校园内有个圆形花坛，围绕花坛有n |
