1196 : 好吃的甜品
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 128 兆MB
- 提交次数Submitted
- 749 次Times
- 通过次数Solved
- 131 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
X国有n个城市,编号为1, 2, …, n,城市之间由m条双向道路相连. 小明和小红住在X国不同的城市里,今天小明希望带上最新出的网红甜品去小红家玩,但是这个网红甜品只在少数几个城市才能买到,于是小明想让你帮忙计算一下从家里出发买完甜品之后去小红家的最短路程.
输入格式Input
包含不超过20组测试数据。
每组测试数据的第一行包含6个整数n、m、k、s、t、w,其中:
- n表示城市的数量
- m表示城市间道路的数量
- k表示甜品店的数量
- s表示小明所在城市的编号
- t表示小红所在城市的编号
- w表示小明想买的甜品的数量
接下来m行每行包含3个整数ai、bi、ci,表示编号为ai的城市和编号为bi的城市之间有一条长度为ci的双向道路. 接下来k行每行包含2个整数xj、yj,表示第j个甜品店所在城市的编号为xj,该门店一共有yj个甜品.
数据保证所有城市之间是连通的.
- 3 ≤ n ≤ 103
- n ≤ m ≤ 104
- 1 ≤ k ≤ min (16,n)
- 1 ≤ ci ≤ 103
- 1 ≤ yj ≤ 103
- $1 \leq w \leq \sum_{j=1}^{k} y_j$
输出格式Output
对于每组测试数据,输出小明从家里出发并在途中买够甜品去小红家最短的总路程.
样例Sample
出题Author
Staginner
来源Source
湖南省第十八届大学生计算机程序设计竞赛(HNCPC2022)
题目到此结束End of problem