云市置换账本

题目描述

云市中共有 $n$ 种货物，编号为 $0$ 到 $n-1$，其中第 $i$ 种货物的账面价值为 $v_i$。

市集中共有 $m$ 位置换商。对于第 $j$ 位置换商，如果你手上拿着货物 $x_j$，就可以和他交换成货物 $y_j$。

每次置换时，商人都会按照账面价值结算差额：

• 如果新货物更贵，你需要补上差额；
• 如果新货物更便宜，你会拿回差额；
• 无论如何，这次置换都会再额外收取 $1$ 枚银片作为手续钱。

你一开始拥有货物 $a$，目标是得到货物 $b$。

请你求出：完成目标所需的最小花费。如果这个最小花费是负数，表示你在完成目标的同时反而赚到了银片。

如果无法得到货物 $b$，请输出 No solution。

输入格式

第一行包含四个整数 $n, m, a, b$。

第二行包含 $n$ 个整数 $v_0, v_1, \dots, v_{n-1}$。

接下来 $m$ 行，每行包含两个整数 $x_j, y_j$，表示一位置换商的规则。

输出格式

输出最小花费；如果无解，输出 No solution。

输入输出样例 #1

输入 #1

3 5 0 2
1 2 4
1 0
2 0
0 1
2 1
1 2

输出 #1

5

输入输出样例 #2

输入 #2

3 3 0 2
100 2 4
0 1
1 2
0 2

输出 #2

-95

输入输出样例 #3

输入 #3

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

输出 #3

No solution

数据范围

对于 $30\%$ 的数据，$1 \le n \le 10$，$0 \le m \le 20$。

对于 $70\%$ 的数据，$1 \le n \le 10^3$，$0 \le m \le 10^4$。

对于 $100\%$ 的数据，$1 \le n \le 10^5$，$0 \le m \le 2 \times 10^5$，$1 \le v_i \le 10^9$。

建议

一刷、二刷、三刷