2.零食店 (snackstore.pas/c/cpp)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【问题描述】
成功找到了学长之后学姐感觉到有些饿,于是决定去附近的零食店给自己和学长买些零食。
焦作市的有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个询问的要求下有多少家零食店可供学姐挑选。

【输入输出样例1】
snackstore.in snackstore.out
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】
snackstore.in snackstore.out
提供大样例
【数据范围】
样例中第一个询问能去编号为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。

2019年6月15日高一(第二学期)模拟测试(九)---补题目通道

未参加
状态
已结束
规则
ACM/ICPC
题目
4
开始于
2019-06-15 12:00
结束于
2019-07-10 12:00
持续时间
600.0 小时
主持人
参赛人数
15