UVA10099 The Tourist Guide
题目描述
有 $N\ (N\le 100)$ 个城市，城市间有许多条双向通行的道路，每条道路连接两座城市。每条道路还有一个权值 $P\ (P>1)$，表示在该条道路上行驶的车辆被允许的最大载客量。G 先生是一名导游，他想要**亲自**把 $num$ 名旅客从 $S$ 城运往 $T$ 城，问 G 先生最少要运多少趟？
如上图，G 先生想要**亲自**把 $99$ 名旅客从 $1$ 号城运往 $7$ 号城。他应走的路径为 $1-2-4-7$，路径上最大载客量的最小值为 $25$，按理运 $4$ 趟即可。但因为 G 先生也是人，所以实际上每次只能运输 $24$ 名旅客，需要运 $5$ 次。
输入格式
**本题有多组数据**。
对于每组数据：
第一行两个正整数 $N$ 和 $M$，表示城市数量和道路数量。
接下来 $M$ 行，每行三个正整数 $u,v,w$，表示城市 $u$ 和城市 $v$ 由一条最大载客量为 $w$ 的道路连接。
最后一行三个正整数 $S,T,num$，表示要将 $num$ 名旅客从 $S$ 城运往 $T$ 城。
当 $N$ 和 $M$ 为 $0$ 时停止输入。
输出格式
每组数据输出两行：
第一行，输出 “Scenario #x”，x 为当前是第几组数据。
第二行，输出 “Minimum Number of Trips = ans”，ans 为所求答案。
**每组输出最后应输出两次换行。**