QOJ.ac

QOJ

حد الوقت: 1 s حد الذاكرة: 512 MB مجموع النقاط: 100

#4508. 货币转移

الإحصائيات

Sonia 是西南经济研究联盟 (SWERC) 的首席执行官。SWERC 的主要资产是一组分布在多个国家的银行,这些银行专门从事这些国家之间的电汇业务。

银行之间通过转账协议进行资金转移。每当这些银行之间发生转账时,此类协议都会确定一笔固定费用。当客户希望将资金转账到不同银行的账户时,资金会在有转账协议的银行之间流动,直到到达目标账户。对于每一笔中间交易,客户都必须支付相应的转账费用。

SWERC 的目标是仅使用其旗下的银行作为中介,为客户提供最便宜的费用,并从中赚取佣金。在最近的经济危机之前,一切进展顺利。由于当前形势,各国政府同意对每笔电汇征收额外税款。他们的目标既是增加税收收入,又避免资金流向世界各地的避税天堂。因此,他们的意图是尽可能提高这笔额外税款(同时避免引起过多的动荡)。

Sonia 是一位精明的执行官,她想利用这种情况,确保 SWERC 提供在银行 $X$ 和 $Y$(他们最频繁的转账请求)之间转账的最便宜方式。她将尝试游说政客,以便新的费用能实现这一目标。她收集了关于银行之间(包括竞争对手)转账协议的数据,但不知道新费用的数值应该是多少。

任务

你能帮助 Sonia 计算出最大的费用,使得 SWERC 能够提供在 $X$ 和 $Y$ 之间转账的最便宜方式吗?

输入格式

第一行包含四个空格分隔的整数:$N, P, X, Y$,分别表示现有银行的数量、转账合作关系的数量以及银行 $X$ 和 $Y$ 的标识符。接下来的 $P$ 行包含三个空格分隔的整数:$a_i, b_i, c_i$,表示银行 $a_i$ 和 $b_i$ 之间存在费用为 $c_i$ 的合作关系。

随后是一行包含一个整数 $M$,表示 SWERC 拥有的银行数量。下一行包含 $M$ 个空格分隔的整数,即这些银行的标识符。$X$ 和 $Y$ 总是在此列表中。

数据范围

$2 \le M \le N \le 1\,000$ 且 $1 \le P \le 10\,000$ $1 \le X, Y, a_i, b_i \le N$ 且 $X \neq Y$ 且 $a_i \neq b_i$ $1 \le c_i \le 1\,000\,000\,000$

输出格式

输出应为一个大于零的整数:使得 SWERC 能够提供在 $X$ 和 $Y$ 之间转账的最便宜方式的最大费用。但是,如果没有这样的值可以实现这一点,则输出 Impossible。如果每笔转账的费用可以无限大,则输出 Infinity

样例

输入格式 1

6 8 1 6
1 2 5
1 3 1
2 6 6
2 3 6
4 2 3
3 4 1
4 5 1
5 6 1
5
1 3 6 5 4

输出格式 1

3

说明

如果额外费用为 4 或更多,则 SWERC 无法提供最便宜的交易费用。例如:如果费用为 4,SWERC 提供的成本为 20,依次使用银行 1、3、4、5 和 6。然而,使用银行 2 作为中介,我们只需支付 19。

输入格式 2

3 4 1 2
1 2 6
1 3 2
1 2 7
2 3 3
2
1 2

输出格式 2

Infinity

输入格式 3

4 4 1 4
1 2 1
1 3 1
2 4 1
3 4 1
3
1 2 4

输出格式 3

Impossible

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.