洛谷P2888 [USACO07NOV]Cow Hurdles S 题解

news/2025/2/14 16:26:21/

洛谷P2888 [USACO07NOV]Cow Hurdles S 题解

题目链接:P2888 [USACO07NOV]Cow Hurdles S

题意:Farmer John 想让她的奶牛准备郡级跳跃比赛,贝茜和她的伙伴们正在练习跨栏。她们很累,所以她们想消耗最少的能量来跨栏。 显然,对于一头奶牛跳过几个矮栏是很容易的,但是高栏却很难。于是,奶牛们总是关心路径上最高的栏的高度。 奶牛的训练场中有 N ( 1 ≤ N ≤ 300 ) N (1 ≤ N ≤ 300) N(1N300) 个站台,分别标记为 1 … N 1\dots N 1N 。所有站台之间有 M ( 1 ≤ M ≤ 25 , 000 ) M (1 ≤ M ≤ 25,000) M(1M25,000) 条单向路径,第i条路经是从站台 S i S_i Si 开始,到站台 E i E_i Ei ,其中最高的栏的高度为 H i ( 1 ≤ H i ≤ 1 , 000 , 000 ) H_i (1 ≤ H_i ≤ 1,000,000) Hi(1Hi1,000,000)。无论如何跑,奶牛们都要跨栏。 奶牛们有 T ( 1 ≤ T ≤ 40 , 000 ) T (1 ≤ T ≤ 40,000) T(1T40,000) 个训练任务要完成。第 i i i 个任务包含两个数字 A i A_i Ai B i ( 1 ≤ A i ≤ N ; 1 ≤ B i ≤ N ) B_i (1 ≤ A_i ≤ N; 1 ≤ B_i ≤ N) Bi(1AiN;1BiN),表示奶牛必须从站台 A i A_i Ai 跑到站台 B i B_i Bi ,可以路过别的站台。奶牛们想找一条路径从站台 A i A_i Ai 到站台 B i B_i Bi ,使路径上最高的栏的高度最小。 你的任务就是写一个程序,计算出路径上最高的栏的高度的最小值。

分析题目可以发现这是一张具有非负权重的有向图

我们只需要找到一条路径使得这条路径上所有的边权中最大值最小即可

Floyd解法

别看这个 n ≤ 300 n\le300 n300 ,跑起来还是飞快地(数据有点水)

容易推出方程 f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));

不过我有点不放心就加了个小剪枝 qwq 虽然只快了3ms

代码如下

//Floyd
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>void read(T &k)
{char ch=gc();T x=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}k=x*f;
}
template<typename T>void write(T k)
{if(k<0){k=-k;pc('-');}if(k>9)write(k/10);pc(k%10+'0');
}
int n,m,Q,f[305][305];
signed main()
{read(n);read(m);read(Q);for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)f[i][j]=INF;for(int i=1,u,v,w; i<=m; i++){read(u);read(v);read(w);f[u][v]=min(f[u][v],w);}for(int k=1; k<=n; k++)for(int i=1; i<=n; i++)if(f[i][k]!=INF)for(int j=1; j<=n; j++)f[i][j]=min(f[i][j],max(f[i][k],f[k][j]));while(Q--){int x,y;read(x);read(y);write((f[x][y]==INF)?-1:f[x][y]);pc('\n');}return 0;
}

其他解法

关于SPFA,她死了。

开个玩笑而已

不过我们可以用理论复杂度较低的dijkstra

注意到 N ≤ 300 N\le300 N300

那么离线解决即可

时间复杂度 O ( N 2 log ⁡ M + T ) O(N^2\log M + T) O(N2logM+T)

不过实际情况下由于dijkstra常数较大,跑的甚至比Floyd慢…

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define gc() getchar()
#define pc(a) putchar(a)
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T>void read(T &k)
{char ch=gc();T x=0,f=1;while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}k=x*f;
}
template<typename T>void write(T k)
{if(k<0){k=-k;pc('-');}if(k>9)write(k/10);pc(k%10+'0');
}
struct Edge
{int u,v,w,next;
}e[50005];
struct node
{int u,mn;bool operator<(const node &o)const{return mn>o.mn;}
};
int pos=1,head[305];
int n,m,Q,d[305][305],vis[305];
void addEdge(int u,int v,int w)
{e[pos]={u,v,w,head[u]};head[u]=pos++;
}
void dijkstra(int st)
{priority_queue<node> q;memset(vis,0,sizeof(vis));for(int i=1; i<=n; i++)d[st][i]=INF;q.push({st,INF});while(!q.empty()){int u=q.top().u;q.pop();if(vis[u])continue;vis[u]=1;for(int i=head[u]; i; i=e[i].next){int v=e[i].v,t=max(d[st][u],e[i].w);if(t==INF)t=e[i].w;if(d[st][v]>t){d[st][v]=t;if(!vis[v])q.push({v,d[st][v]});}}}
}
signed main()
{read(n);read(m);read(Q);for(int i=1,u,v,w; i<=m; i++){read(u);read(v);read(w);addEdge(u,v,w);}for(int i=1; i<=n; i++)dijkstra(i);while(Q--){int x,y;read(x);read(y);write((d[x][y]==INF)?-1:d[x][y]);pc('\n');}return 0;
}

转载请说明出处


http://www.ppmy.cn/news/628803.html

相关文章

洛谷P2768

二分真的好难/(ㄒoㄒ)/~~&#xff01; 首先看题&#xff0c;题目中我们可以知道选手跳跃最短距离的最大值&#xff0c;所以我们可以使用二分。 判断是否需要二分可以看题目中是否有类似求最短距离的最大值或者最大距离的最小值。 那么本题怎么进行二分呢 我们可以以整段距离…

Buffalo框架的使用

【整体介绍&#xff0c;建议先看完下面的内容在回过来看这个介绍】当用户输入账号密码后&#xff0c;点击“提交”按钮&#xff0c;则执行JSh中的getInfo()方法&#xff0c;该方法会调用Buffalo框架中的remoteCall("UserService.getInfo",[username,password],functi…

洛谷 AT_abc178_b [ABC178B] Product Max

洛谷 AT_abc178_b [ABC178B] Product Max 1、题目题面翻译题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 样例 #3样例输入 #3样例输出 #3 提示制約Sample Explanation 1Sample Explanation 2 2、翻译题面&#xff1a; AC代码&#xff…

洛谷P1077摆花

文章目录 一、题目描述二、思路三、代码 一、题目描述 https://www.luogu.com.cn/problem/P1077 题目描述很容易看懂 二、思路 动态规划题目&#xff0c;首先定义状态 dp[i][j]:摆前i种花&#xff0c;一共摆j盆的方案数。 i&#xff1a;1~n j&#xff1a;1~m 需要注意的时&a…

IP地点定位为什么有误差?

随着互联网的不断普及&#xff0c;人们对IP地点定位需求越来越多。然而&#xff0c;即便是在现代技术的支持下IP地点定位仍然存在误差。那么&#xff0c;IP地点定位为什么会出现误差呢&#xff1f; IP&#xff08;Internet Protocol&#xff09;地址是指互联网协议&#xff08;…

数据库技术之MySQL高级

目录 子查询与表连接 子查询(嵌套sql) 利⽤⼦查询进⾏过滤 作为计算字段使⽤⼦查询 外键 表关系 关系表 表联结 联结多个表 使⽤表别名 AS 组合查询 UNION 总结&#xff1a;表联结 练习题 sql_mode sql_mode值的含义 MySQL事务 概述 ⼀,事务的语法 ⼆,事务的…

一篇博客帮你了解MySQL高级知识

MySQL高级 一、子查询与表连接子查询&#xff08;嵌套SQL&#xff09;关系表组合查询 UNION 二、MySQL事务概述事务的语法事务的ACID特性事物的并发问题事物的的隔离级别不同隔离级别的锁的情况&#xff08;了解&#xff09;隐式提交&#xff08;了解&#xff09; 三、MySQL中的…

构建高并发平台架构

一、 设计理念 1. 空间换时间 1) 多级缓存&#xff0c;静态化 客户端页面缓存&#xff08;http header中包含Expires/Cache of Control&#xff0c;last modified(304&#xff0c;server不返回body&#xff0c;客户端可以继续用cache&#xff0c;减少流量)&#xf…