P1396 营救[最短路+二分]
2024-09-05 04:49:18
题目描述
“咚咚咚……”“查水表!”原来是查水表来了,现在哪里找这么热心上门的查表员啊!小明感动的热泪盈眶,开起了门……
妈妈下班回家,街坊邻居说小明被一群陌生人强行押上了警车!妈妈丰富的经验告诉她小明被带到了t区,而自己在s区。
该市有m条大道连接n个区,一条大道将两个区相连接,每个大道有一个拥挤度。小明的妈妈虽然很着急,但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从s至t的路线,使得经过道路的拥挤度最大值最小。
输入输出格式
输入格式:
第一行四个数字n,m,s,t。
接下来m行,每行三个数字,分别表示两个区和拥挤度。
(有可能两个区之间有多条大道相连。)
输出格式:
输出题目要求的拥挤度。
输入输出样例
输入样例#1:
3 3 1 3
1 2 2
2 3 1
1 3 3
输出样例#1:
2
说明
数据范围
30% n<=10
60% n<=100
100% n<=10000,m<=2n,拥挤度<=10000
题目保证1<=s,t<=n且s<>t,保证可以从s区出发到t区。
样例解释:
小明的妈妈要从1号点去3号点,最优路线为1->2->3。
解析:
跟P1462这题几乎一毛一样,可以看我以前发的博客,比较详细。当然,之所以P1462是蓝题,主要是数据(可能吧)。
依旧是是用二分来约束最短路径上经过的的最大边权值,是一种比较巧妙的思路吧。
参考代码:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define N 20010
#define INF 23333333
using namespace std;
struct rec{
int next,ver,edge;
}g[N<<];
int head[N],tot,n,m,s,t,d[N],f[N<<];
bool v[N];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
void add(int x,int y,int val)
{
g[++tot].ver=y,g[tot].edge=val;
g[tot].next=head[x],head[x]=tot;
}
bool dijkstra(int x,int k)
{
memset(v,,sizeof(v));
memset(d,0x3f,sizeof(d));
d[x]=;
q.push(make_pair(,x));
while(q.size())
{
int index=q.top().second;q.pop();
if(v[index]) continue;
v[index]=;
for(int i=head[index];i;i=g[i].next){
int y=g[i].ver,z=g[i].edge;
if(d[y]>d[index]+z&&f[k]>=z){
d[y]=d[index]+z;
q.push(make_pair(d[y],y));
}
}
}
if(d[t]>INF) return ;
else return ;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=;i<=m;i++){
int x,y,val;
scanf("%d%d%d",&x,&y,&val);
f[i]=val;
add(x,y,val),add(y,x,val);
}
//¶þ·Ö
sort(f+,f+n+);
int l=,r=n,mid;
while(l<=r)
{
mid=(l+r)>>;
if(dijkstra(s,mid)) r=mid-;
else l=mid+;
}
cout<<f[l]<<endl;
return ;
}
啊咧?怎么乱码了?(逃
最新文章
- await之后的线程问题
- Android EditText使用详解
- 去掉网址中的 html编码
- CSS知识点补充
- 规范 : 过程 : login cookies sessionTimeOut
- 【CNMP系列】VIM编辑器详解
- 十分钟搭建redis单机版 &; java接口调用
- 基于Jmeter的轻量级接口压力测试(一)
- 自动化制作.framework
- 微信jssdk config:invalid signature 签名错误 ,问题排查过程
- RabbitMQ通过Exchange.Direct、同一个队列绑定不同的routekey实现不同的消费
- Intel Code Challenge Final Round (Div. 1 + Div. 2, Combined)
- 简单的if多分支结构练习:用户录入 1-10的数字 , 1-7没奖品 , 8,9,10分别获得 3 2 1 等奖
- UART、SPI和I2C详解
- 移动端根据不同DPR加载大小不同的图片
- luogu1975 [国家集训队]排队
- arp欺骗图解
- js gettext
- nodejs加载模块心得,mongoose的继承,schematype的mixd介绍
- SpringBoot整合MyBatis及Thymeleaf