题目描述
有 N (N≤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 为所求答案。
每组输出最后应输出两次换行。