4596: 好吃的甜品
内存限制：128 MB
时间限制：1 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：0
通过：0
题目描述
X国有n个城市，编号为1, 2, …, n，城市之间由m条双向道路相连. 小明和小红住在X国不同的城市里，今天小明希望带上最新出的网红甜品去小红家玩，但是这个网红甜品只在少数几个城市才能买到，于是小明想让你帮忙计算一下从家里出发买完甜品之后去小红家的最短路程.
输入格式
包含不超过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
输出格式
对于每组测试数据，输出小明从家里出发并在途中买够甜品去小红家最短的总路程.
输入样例 复制
3 2 1 1 3 2
1 2 1
1 3 2
2 3
4 4 2 1 3 2
1 2 3
2 3 2
1 4 6
3 4 3
2 2
4 3
4 4 2 1 3 5
1 2 3
2 3 2
1 4 6
3 4 3
2 4
4 3输出样例 复制
4
5
11