| 题目名称 | 2507. 零食店 |
|---|---|
| 输入输出 | snackstore.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 前鬼后鬼的守护
于2016-10-19加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：61， 提交：581， 通过率：10.5% | ||||
 健康铀 |
100 | 0.031 s | 3.28 MiB | C++ |
|
wdsjl |
100 | 0.032 s | 3.39 MiB | C++ |
 紫葉 |
100 | 0.906 s | 4.74 MiB | C++ |
 Samle |
100 | 1.147 s | 5.49 MiB | C++ |
 sdfzxh |
100 | 1.163 s | 9.20 MiB | C++ |
 再见 |
100 | 1.183 s | 5.42 MiB | C++ |
 891922758 |
100 | 1.222 s | 5.44 MiB | C++ |
 Anson |
100 | 1.227 s | 5.44 MiB | C++ |
 spli |
100 | 1.239 s | 5.39 MiB | C++ |
 Ostmbh |
100 | 1.261 s | 5.37 MiB | C++ |
| 本题关联比赛 | |||
| NOIP模拟赛by mzx Day1 | |||
| 防止浮躁的小练习v0.7 | |||
| 模拟训练 | |||
| 2024国庆练习1 | |||
| 2024国庆练习1 | |||
| 关于 零食店 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @xzz_233 :
您太强了  Mayuri
2017-08-25 19:32
14楼
| ||||
|
我真蠢。。。
snackstore->snakestore | ||||
|
数据未修复，请写题的人把不存在的边边权设成1e9+1。
再见
2017-07-23 09:06
12楼
| ||||
|
再见
2016-11-10 22:06
11楼
| ||||
|
这题数据如果是这样的话，那跑出来的答案应该是不正确的。
我猜想std中的极大值设为了1e9+1，数据中出现1e9+1，使得图中一些不能联通的点联通了。 答案就不对了。 std容错太差了吧= = maya终于A了，还得加终极读优 | ||||
|
回复 @Rapiz :
能不能解释一下这样的原因..  yveh
2016-11-06 15:18
9楼
| ||||
|
回复 @sherc :
请问为什么会这样... yveh
2016-11-06 14:49
8楼
| ||||
|
数据有误，数据中询问有最大路径 d等于1e9+1
如果把没有的边权值设为1e9+1就能A 设成更大的就过不去了 8,9,10组应该都有问题，第8组 921161个询问对应最大值就是1e9+1，答案输出了96（所有的点），正确应该是88 再见
2016-10-21 18:04
6楼
| ||||
|
最大值请赋1e9+1……
0x3f调了一天  Rapiz
2016-10-21 17:37
5楼
| ||||
xzz_233
FoolMike【题目描述】
成功找到了学长之后学姐感觉到有些饿，于是决定去附近的零食店给自己和学长买些零食。
焦作市的有n家零食店，由m条道路连接着这些零食店，每条道路都有自己的长度l，每家零食店都有自己的消费指数。
由于学姐是个穷B，所以去买零食的路上不能经过某些消费指数超过一定限度的店。
同时由于学姐体力有限，所以去买零食的过程中走的路程不能太长。
想来想去学姐决定去问学长买什么零食比较好，反正到最后都是学长吃╮(╯_╰)╭
在去问之前，学姐准备先做好准备，她把焦作市（所有零食店）的地图给了你，希望你能编出一个程序快速回答她从某个零食店出发，在上述限制下有多少家零食店可供她挑选。
【输入格式】
第一行三个正整数n，m，q，分别代表零食店数，道路数和询问数。
接下来一行n个正整数，第i个正整数vi代表第i家零食店的消费指数。
接下来m行，第i行三个正整数x,y,l,代表第i条道路连接编号为x和y的两个零食店，长度为l。
接下来q行第i行三个正整数s,c,d，代表第i个询问要求从s出发，所经过的零食店的消费指数不能超过c（除了起点和终点以外），且行走路程不超过d。
【输出格式】
一共q行，第i行一个整数代表在第i个询问的要求下有多少家零食店可供学姐挑选。
【样例输入】
5 5 2 1 2 3 4 5 1 2 1 1 3 4 2 3 2 1 4 3 2 5 1 1 1 3 2 1 2
【样例输出】
2 3
【提示】
样例中第一个询问能去编号为2/4的零食店。
第二个询问能去编号为1/3/5的零食店。
对于40%的数据，n≤10，m≤20，q=1。
对于70%的数据，m≤500，q≤10000。
对于100%的数据，n≤100，m≤10000，q≤1000000，vi,c,d≤10^9，1≤x,y,s≤n，l≤10^6。
【来源】
mzx