SP3305 SA04C - Roman Patrollers

在古代，罗马帝国通过巡逻员来确保所有城市都在掌控之中。作为巡逻员，他们的任务是不断地访问这些城市，尽可能缩短两次访问同一城市之间的时间间隔。为此，军事协会（MS）希望模拟巡逻员的行为，从而评估其有效性。 模拟中的每个周期代表一个时间单位。在模拟进行到第 $T$ 个周期时，城市 $X$ 的瞬时闲置时间（ICI）是指自巡逻员最后一次访问城市 $X$ 以来经过的周期数。初始时，所有城市的瞬时闲置时间为零。在每个周期结束时，瞬时帝国闲置时间（IEI）为当时所有城市的瞬时闲置时间之和。整个模拟过程的帝国闲置时间（EI）则是全部 $N$ 个周期中每个周期结束后的瞬时帝国闲置时间之和。 巡逻员访问城市 $X$ 之后，总是选择前往瞬时闲置时间最高的邻近城市 $Y$（若有多个城市相同，则选取编号最小的）。如果有一条道路直接连接两个城市 $X$ 和 $Y$，则 $X$ 和 $Y$ 被认为是邻近的。在模拟开始时，巡逻员位于某一城市，并获得一张罗马帝国的地图，其中包括道路的信息，显示每条道路的长度（以公里为单位）以及所连接的城市。任何连接城市 $X$ 和 $Y$ 的道路都是双向可通行的。 假设巡逻员每次旅行1公里需要一个时间单位（即一个模拟周期），并且在城市中停留的时间可以忽略不计（视为零）。MS 要求你计算出经过 $N$ 个模拟周期后的帝国闲置时间。 为了方便理解，考虑一个包含三个城市（1、2和3）的帝国，有两条长度为1公里的道路。第一条道路连接城市1和2，第二条道路连接城市2和3。下面是从城市1开始的3周期模拟的运行情况： - 模拟开始时： - 巡逻员位于：1 - ICI1 = 0, ICI2 = 0, ICI3 = 0 - IEI = 0 - EI = 0 - 第1个周期后： - 巡逻员位于：2 - ICI1 = 1, ICI2 = 0, ICI3 = 1 - IEI = 2 - EI = 2 - 第2个周期后： - 巡逻员位于：1 - ICI1 = 0, ICI2 = 1, ICI3 = 2 - IEI = 3 - EI = 5 - 第3个周期后： - 巡逻员位于：2 - ICI1 = 1, ICI2 = 0, ICI3 = 3 - IEI = 4 - EI = 9 对于这个场景，模拟3个周期后的帝国闲置时间是9。

输入包括多个测试用例。每个测试用例的第一行为四个整数 $C$、$R$、$N$ 和 $S$，依次表示帝国中的城市数量（$2 \le C \le 1000$）、道路数量（$1 \le R \le C(C - 1)/2$）、模拟周期数（$1 \le N \le 1000$）和巡逻员的起始城市编号（$1 \le S \le C$）。城市由1到$C$之间的唯一整数标识。接下来的 $R$ 行，每行包含三个整数 $X$、$Y$ 和 $D$，描述一条道路：$X$ 和 $Y$ 是两个不同的城市编号（$1 \le X \neq Y \le C$），$D$ 为连接 $X$ 和 $Y$ 的这条道路的长度（$1 \le D \le 1000$）。每对城市之间的道路信息在输入中最多出现一次。可以假设，通过给定道路，可以从任何一个城市到达另一个城市。输入的终止标志为 $C = R = N = S = 0$。

对于每个测试用例，输出经过 $N$ 次模拟后的帝国闲置时间，以一行整数表示。 **本翻译由 AI 自动生成**