English · Original
Chinese · Translation
Formal · Original
Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has _n_ junctions, some of which are connected by two-way roads. The length of each road is defined by some positive integer number of meters; the roads can have different lengths.
Initially each junction has exactly one taxi standing there. The taxi driver from the _i_\-th junction agrees to drive Petya (perhaps through several intermediate junctions) to some other junction if the travel distance is not more than _t__i_ meters. Also, the cost of the ride doesn't depend on the distance and is equal to _c__i_ bourles. Taxis can't stop in the middle of a road. **Each taxi can be used no more than once. Petya can catch taxi only in the junction, where it stands initially.**
At the moment Petya is located on the junction _x_ and the volleyball stadium is on the junction _y_. Determine the minimum amount of money Petya will need to drive to the stadium.
## Input
The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 1000, 0 ≤ _m_ ≤ 1000). They are the number of junctions and roads in the city correspondingly. The junctions are numbered from 1 to _n_, inclusive. The next line contains two integers _x_ and _y_ (1 ≤ _x_, _y_ ≤ _n_). They are the numbers of the initial and final junctions correspondingly. Next _m_ lines contain the roads' description. Each road is described by a group of three integers _u__i_, _v__i_, _w__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, 1 ≤ _w__i_ ≤ 109) — they are the numbers of the junctions connected by the road and the length of the road, correspondingly. The next _n_ lines contain _n_ pairs of integers _t__i_ and _c__i_ (1 ≤ _t__i_, _c__i_ ≤ 109), which describe the taxi driver that waits at the _i_\-th junction — the maximum distance he can drive and the drive's cost. The road can't connect the junction with itself, but between a pair of junctions there can be more than one road. All consecutive numbers in each line are separated by exactly one space character.
## Output
If taxis can't drive Petya to the destination point, print "-1" (without the quotes). Otherwise, print the drive's minimum cost.
Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.
[samples]
## Note
An optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.
Petya 非常喜欢排球。一天，他赶往排球比赛时迟到了。Petya 还没有买自己的车，因此他不得不打出租车。这座城市有 #cf_span[n] 个交叉口，其中一些由双向道路连接。每条道路的长度由某个正整数（单位：米）定义；道路长度可以不同。
最初，每个交叉口恰好有一辆出租车停在那里。第 #cf_span[i] 个交叉口的司机同意搭载 Petya（可能经过若干中间交叉口）前往另一个交叉口，前提是行驶距离不超过 #cf_span[ti] 米。此外，车费与距离无关，固定为 #cf_span[ci] 布尔。出租车不能在道路中间停下。*每辆出租车最多只能使用一次。Petya 只能在出租车初始所在的交叉口上车。*
目前 Petya 位于交叉口 #cf_span[x]，排球馆位于交叉口 #cf_span[y]。请确定 Petya 到达场馆所需的最少费用。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000]），分别表示城市中的交叉口数量和道路数量。交叉口编号从 #cf_span[1] 到 #cf_span[n]。下一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]），分别表示起始和终点交叉口。接下来 #cf_span[m] 行描述道路，每条道路由三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9]）描述，分别表示连接的两个交叉口及其道路长度。接下来 #cf_span[n] 行包含 #cf_span[n] 对整数 #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ ti, ci ≤ 10^9]），描述位于第 #cf_span[i] 个交叉口的司机：他能行驶的最大距离和车费。道路不会连接交叉口与自身，但一对交叉口之间可能存在多条道路。每行中相邻数字之间恰好用一个空格分隔。
如果出租车无法将 Petya 送达目的地，请输出 "-1"（不含引号）。否则，输出最小车费。
请勿在 C++ 中使用 %lld 格式符读写 64 位整数。推荐使用 cin、cout 流或 %I64d 格式符。
最优方案：从交叉口 1 到 2（经由交叉口 4），再从 2 到 3。总费用为 7+2=9 布尔。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000]），分别表示城市中的交叉口数量和道路数量。交叉口编号从 #cf_span[1] 到 #cf_span[n]。下一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]），分别表示起始和终点交叉口。接下来 #cf_span[m] 行描述道路，每条道路由三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9]）描述，分别表示连接的两个交叉口及其道路长度。接下来 #cf_span[n] 行包含 #cf_span[n] 对整数 #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ ti, ci ≤ 10^9]），描述位于第 #cf_span[i] 个交叉口的司机：他能行驶的最大距离和车费。道路不会连接交叉口与自身，但一对交叉口之间可能存在多条道路。每行中相邻数字之间恰好用一个空格分隔。
## Output
如果出租车无法将 Petya 送达目的地，请输出 "-1"（不含引号）。否则，输出最小车费。请勿在 C++ 中使用 %lld 格式符读写 64 位整数。推荐使用 cin、cout 流或 %I64d 格式符。
[samples]
## Note
最优方案：从交叉口 1 到 2（经由交叉口 4），再从 2 到 3。总费用为 7+2=9 布尔。
**Definitions**
Let $ n, m \in \mathbb{Z} $ be the number of junctions and roads, respectively.
Let $ G = (V, E) $ be an undirected weighted graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, where each edge $ (u, v) \in E $ has weight $ w(u, v) \in \mathbb{Z}^+ $.
Let $ x, y \in V $ be the source and target junctions, respectively.
For each junction $ i \in V $, let $ t_i \in \mathbb{Z}^+ $ be the maximum travel distance and $ c_i \in \mathbb{Z}^+ $ be the cost of the taxi available at $ i $.
Let $ d(i, j) \in \mathbb{R}_{\geq 0} \cup \{\infty\} $ denote the shortest path distance (in meters) between junctions $ i $ and $ j $ in $ G $, computed using all roads.
**Constraints**
1. $ 1 \leq n \leq 1000 $, $ 0 \leq m \leq 1000 $
2. $ 1 \leq x, y \leq n $
3. $ 1 \leq w(u, v) \leq 10^9 $ for all edges $ (u, v) $
4. $ 1 \leq t_i, c_i \leq 10^9 $ for all $ i \in V $
5. Each taxi at junction $ i $ can be used at most once.
6. Petya can only board a taxi at its initial junction $ i $.
7. A taxi at $ i $ can take Petya to junction $ j $ **iff** $ d(i, j) \leq t_i $.
**Objective**
Find the minimum total cost to travel from $ x $ to $ y $, using a sequence of taxis (each used at most once), such that:
- The first taxi is boarded at $ x $.
- Each subsequent taxi is boarded at the junction where the previous taxi dropped Petya.
- The final junction is $ y $.
Formally, find the minimum value of $ \sum_{k=1}^{\ell} c_{i_k} $ over all sequences $ i_1 = x, i_2, \dots, i_\ell $ such that:
- $ d(i_k, i_{k+1}) \leq t_{i_k} $ for all $ k \in \{1, \dots, \ell-1\} $,
- $ i_\ell = y $,
- All $ i_k \in V $ are distinct (each taxi used at most once).
If no such sequence exists, output $ -1 $.
API Response (JSON)
{
"problem": {
"name": "C. Volleyball",
"description": {
"content": "Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has _n_ junctions, some of which a",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF95C"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has _n_ junctions, some of which a...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Petya 非常喜欢排球。一天，他赶往排球比赛时迟到了。Petya 还没有买自己的车，因此他不得不打出租车。这座城市有 #cf_span[n] 个交叉口，其中一些由双向道路连接。每条道路的长度由某个正整数（单位：米）定义；道路长度可以不同。\n\n最初，每个交叉口恰好有一辆出租车停在那里。第 #cf_span[i] 个交叉口的司机同意搭载 Petya（可能经过若干中间交叉口）前往另一个交叉口，前提是行...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z} $ be the number of junctions and roads, respectively. \nLet $ G = (V, E) $ be an undirected weighted graph with $ V = \\{1, 2, \\dots, n\\} $ and $ E \\subseteq...",
"is_translate": false,
"language": "Formal"
}
]
}