题目背景

2023 年 12 月 GESP C++ 七级编程第 1 题

题目描述

市场上共有 $N$ 种商品，编号从 $0$ 到 $N-1$，第 $i$ 种商品价值 $v_i$ 元。共有 $M$ 个商人，编号从 $0$ 到 $M-1$。在第 $j$ 个商人处，可以用第 $x_j$ 种商品交换第 $y_j$ 种商品。

每次交易的花费为 $v_{y_j}-v_{x_j}+1$，其中 $1$ 元为手续费；若该值为负数，表示这次交易后你反而赚到了钱。

你初始拥有商品 $a$，希望通过若干次交换获得商品 $b$。请计算达成目标的最小总花费；若无法获得商品 $b$，输出 No solution。

输入格式

第一行输入四个整数 $N,M,a,b$，分别表示商品数量、商人数量、初始商品和目标商品。 第二行输入 $N$ 个正整数 $v_0,v_1,ldots,v_{N-1}$。 接下来 $M$ 行，每行输入两个整数 $x_i,y_i$，表示第 $i$ 个商人支持用商品 $x_i$ 交换商品 $y_i$。

输出格式

输出一行。若能够通过交换获得商品 $b$，输出一个整数，表示最少花费；否则输出 No solution。

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

5

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

-95

数据范围与提示

• 对于 $30\%$ 的测试点，保证 $N\le 10$，$M\le 20$。
• 对于 $70\%$ 的测试点，保证 $N\le 10^3$，$M\le 10^4$。
• 对于全部测试点，保证 $2\le N\le 10^5$，$1\le M\le 2\times 10^5$，$0\le a,b,x_i,y_i<N$，$a\ne b$，$x_i\ne y_i$，$1\le v_i\le 10^9$。
• 最小花费可能为负数。

来源

GESP 2023 年 12 月 C++ 七级 T1