SP26349 NINJA6 - TRAVELLING DILEMMA

在这个问题中，我们以一张国家地图为背景，这幅地图包含 $N$ 个城市和 $M$ 条道路。每条道路都连接两个城市。你有两种方式可以从一个城市前往另一个城市： - 乘坐公共交通。 - 驾驶自己的汽车（整个旅程中只能使用一次）。你可以选择使用或不使用这种方式。 地图被表示为一个含有 $N$ 个节点的图（节点编号从 1 到 $N$）。起点是城市 $S$，终点是城市 $D$。每对城市之间有两种路径： - 一种是使用公共交通，成本为 $r$。 - 另一种是使用自己的汽车，成本为 $t$。 你的任务是找出从 $S$ 到 $D$ 的最优路径。这个路径上的旅行成本是最小的，并且可以选择是否使用一次汽车。要求输出从起点到终点的最低旅行成本。 **输入格式：** 第一行输入一个整数 $T$，表示测试用例的数量。 对于每个测试用例： 第一行输入两个用空格分隔的整数 $N$ 和 $M$，分别表示城市数量和道路数量。 接下来 $M$ 行，每行输入四个用空格分隔的整数 $c1$、$c2$、$r$ 和 $t$，其中 $c1$ 和 $c2$ 表示由道路连接的两个城市，$r$ 是使用公共交通的成本，$t$ 是使用自己汽车的成本。 最后一行输入两个空格分隔的整数 $S$ 和 $D$，分别表示起点城市和终点城市。 **输出格式：** 对于每个测试用例，输出从起点到终点的最小旅行成本。如果无法从起点 $S$ 到达终点 $D$，则输出 $-1$。 **数据范围与提示：** - 测试用例数 $1 \le T \le 100$ - 城市数量 $2 \le N \le 1000$ - 道路数量 $1 \le M \le 10000$ - 公共交通和汽车的单程成本 $1 \le r, t \le 10^6$ - 起点和终点城市编号 $1 \le S, D \le N$ **样例输入：** ``` 1 4 5 1 2 6 5 1 3 4 5 2 3 6 1 2 4 3 4 3 4 5 7 1 4 ``` **样例输出：** ``` 8 ``` **本翻译由 AI 自动生成**

无

无