题目名称	2404. [NOI 2013]快餐店
输入输出	`foodshop.in/out`
难度等级	★★★★
时间限制	2000 ms (2 s)
内存限制	512 MiB
测试数据	20
题目来源	TenderRun 于2016-07-30加入
开放分组	全部用户
提交状态
分类标签	二分法贪心 NOI 基环树基环树DP
	分享题解

题目名称

2404. [NOI 2013]快餐店

输入输出

foodshop.in/out

难度等级

★★★★

时间限制

2000 ms (2 s)

内存限制

512 MiB

测试数据

题目来源

TenderRun 于2016-07-30加入

开放分组

全部用户

提交状态

分类标签

二分法贪心 NOI 基环树基环树DP

分享题解

关于快餐店的近10条评论(全部评论)
答辩 ┭┮﹏┭┮ 2024-01-04 20:33 6楼
边表开小了。。。。。再见 2017-05-05 13:11 5楼
回复 @TenderRun : @TenderRun 能解释一下您代码中的v1,v2,u1,u2,Mx,sum的含义吗？顺道说一下下面代码的含义。谢谢。 `for(int i=1;i<=top;i++){ sum+=b[i-1]; u1[i]=max(u1[i-1],sum+dis[stack[i]]); v1[i]=max(v1[i-1],sum+dis[stack[i]]+Mx); Mx=max(Mx,dis[stack[i]]-sum); }` bbsh 2017-02-18 21:23 4楼
回复 @Mike is Fool : 你回复我了，我并不知道，cogs从来不提醒的 TenderRun 2016-11-13 17:50 3楼
二分复杂度是O(nlognlogans)，还得卡卡常！话说COGS真慢，UOJ上#19在1.3s出解，这里得4.8s! 除了#18#19，其他点一共用的似乎还不到1s FoolMike 2016-11-13 10:54 2楼
@TenderRun 把时限改改吧，官方都是2s，512M，非要卡我二分的常数。还有一句，这种代码一定不要隔夜，今天发现昨天写的全是WA点，要不为啥挂了这本多次！ FoolMike 2016-09-13 13:48 1楼

关于 快餐店 的近10条评论(全部评论)

答辩

┭┮﹏┭┮

2024-01-04 20:33 6楼

边表开小了。。。。。

再见

2017-05-05 13:11 5楼

回复 @TenderRun : @TenderRun
能解释一下您代码中的v1,v2,u1,u2,Mx,sum的含义吗？
顺道说一下下面代码的含义。
谢谢。



for(int i=1;i<=top;i++){

 sum+=b[i-1];

 u1[i]=max(u1[i-1],sum+dis[stack[i]]);

 v1[i]=max(v1[i-1],sum+dis[stack[i]]+Mx);

 Mx=max(Mx,dis[stack[i]]-sum);

 }

bbsh

2017-02-18 21:23 4楼

回复 @Mike is Fool :
你回复我了，我并不知道，cogs从来不提醒的

TenderRun

2016-11-13 17:50 3楼

二分复杂度是O(nlognlogans)，还得卡卡常！
话说COGS真慢，UOJ上#19在1.3s出解，这里得4.8s!
除了#18#19，其他点一共用的似乎还不到1s

FoolMike

2016-11-13 10:54 2楼

@TenderRun
把时限改改吧，官方都是2s，512M，非要卡我二分的常数。
还有一句，这种代码一定不要隔夜，今天发现昨天写的全是WA点，要不为啥挂了这本多次！

FoolMike

2016-09-13 13:48 1楼

2404. [NOI 2013]快餐店

★★★★ 输入文件：foodshop.in 输出文件：foodshop.out 简单对比
时间限制：2 s 内存限制：512 MiB

【题目描述】

小T打算在城市C开设一家外送快餐店。送餐到某一个地点的时间与外卖店到该地点之间最短路径长度是成正比的，小T希望快餐店的地址选在离最远的顾客距离最近的地方。快餐店的顾客分布在城市C的N 个建筑中，这N 个建筑通过恰好N 条双向道路连接起来，不存在任何两条道路连接了相同的两个建筑。任意两个建筑之间至少存在一条由双向道路连接而成的路径。小T的快餐店可以开设在任一建筑中，也可以开设在任意一条道路的某个位置上（该位置与道路两端的建筑的距离不一定是整数）。现给定城市C的地图（道路分布及其长度），请找出最佳的快餐店选址，输出其与最远的顾客之间的距离。

【输入格式】

第一行包含一个整数N，表示城市C中的建筑和道路数目。
接下来N行，每行3个整数，Ai，Bi，Li（1≤i≤N；Li>0），表示一条道路连接了建筑Ai与Bi，其长度为Li 。

【输出格式】

仅包含一个实数，四舍五入保留恰好一位小数，表示最佳快餐店选址距离最远用户的距离。
注意：你的结果必须恰好有一位小数，小数位数不正确不得分。

【样例输入】

【样例输出】

2.0

【提示】

数据范围

对于 10%的数据，N<=80,Li=1；

对于 30%的数据，N<=600，Li<=100；

对于 60% 的数据，N<=2000，Li<=10^9；

对于 100% 的数据，N<=10^5，Li<=10^9；

通过：18，提交：41，通过率：43.9%
┭┮﹏┭┮	100	0.220 s	11.53 MiB	C++
j31234	100	0.287 s	8.80 MiB	C++
apt	100	0.297 s	8.40 MiB	C++
lichang	100	0.317 s	8.26 MiB	C++
梦那边的美好ET	100	0.327 s	13.17 MiB	C++
TenderRun	100	0.371 s	8.36 MiB	C++
bbsh	100	0.381 s	10.33 MiB	C++
TenderRun	100	0.391 s	9.81 MiB	C++
Cydiater	100	0.409 s	24.16 MiB	C++
Link	100	0.412 s	5.58 MiB	C++