For a positive integer $$$x$$$, define the cascading sum of $$$x$$$ as the sum of all of $$$x$$$'s nonempty prefixes.
For example, the cascading sum of $$$2023$$$ is $$$2023+202+20+2=2247$$$.
You are given $$$q$$$ queries, where each query gives you a positive integer $$$n$$$. For each query, output the number of positive integers $$$m$$$ such that $$$m \le n$$$ and $$$m$$$ is not the cascading sum of any number.
The first line consists of an integer $$$q$$$, the number of queries ($$$1 \leq q \leq 10^5$$$). The description of the queries follows.
The first line of each query contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^{18})$$$.
For each query, output the number of positive values which are not cascading sums and are at most $$$n$$$.
5 4 10 220 3000 3500
0 1 21 299 349
For the first query, $$$m = 1, 2, 3, 4$$$ are all cascading sums. For example, $$$3$$$ is the cascading sum of $$$3$$$. Therefore, there are $$$0$$$ values.
For the second query, $$$10$$$ is the only value which is not a cascading sum, so there is $$$1$$$ value.
Problem Credits: Anonymous Red Panda
Michael has gotten the internship of a lifetime! He will be working (unpaid, obviously) at Thomas' zoo in the red panda enclosure.
The enclosure can be described as a tree of $$$n$$$ nodes, rooted at node $$$1$$$. Each node contains a house which has exactly one red panda in it. Every afternoon, Michael will be in charge of organized nap-time for the pandas, which involves all $$$n$$$ red pandas reaching the root of the tree to take a nap. It works as follows:
- In one second, Michael may let any number of pandas out of their homes. Then, all pandas that have been let out of their home, other than those at the root, climb up one node in the tree towards the root. The process repeats until Michael has placed all $$$n$$$ pandas.
- If two red pandas ever occupy the same node other than the root, they will start a fight, so this cannot happen.
Note that the panda that lives in node $$$1$$$ must still be let out of its house to join the other pandas (and hug them).
Michael wants to accomplish this task as fast as possible, so he can eat his lunchtime Raisin Brain cereal. What is the minimum time (in seconds) that it will take for Michael to finish placing all pandas, and what is a possible way he can achieve it? Note that Michael will be finished once he places the last panda, not when all pandas reach the root.
The problem has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases.
For each test case, the first line will contain $$$n$$$ ($$$2 \leq n \leq 2\cdot10^5$$$). The next $$$n - 1$$$ lines contain the edges of the tree. Each line will have two integers, $$$u$$$ and $$$v$$$, meaning there is an edge between nodes $$$u$$$ and $$$v$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.
For each test case, print the minimum number of seconds it will take Michael to place the pandas.
Then, in a new line, print $$$i$$$ integers, where the $$$i$$$-th integer is the second during which Michael should let out the panda in node $$$i$$$. If there are multiple possible solutions, print any.
241 23 24 151 21 33 45 3
1 1 1 1 1 2 1 1 1 1 2
For the first test case, Michael can release all pandas at once.
For the second test case, Michael can't release all pandas at once since the pandas at nodes $$$4$$$ and $$$5$$$ will start a fight.
Problem Credits: Allen Wu
It's him and I, Aquemini.
You, the aquamist, are initially given $$$n$$$ stacks that can each hold up to $$$m$$$ blocks. Initially, each stack $$$i$$$ except the $$$n$$$-th stack is full with $$$m$$$ blocks that are all labeled $$$i$$$ (blocks with the same label are indistinguishable from each other). The $$$n$$$-th stack is initially empty, having no blocks on it.
In a single move, you can do the following:
- Take a block off the top of a stack and place it on top of another stack, without causing a stack to have more than $$$m$$$ blocks on it.
You are also given the final arrangement of labeled blocks in each stack, ordered from the bottom to the top of the stack, and your goal is to determine a sequence of moves to get from the initial arrangement to this final arrangement.
The first line contains two integers, $$$n$$$ and $$$m$$$ $$$(3 \le n \le 50, 1 \le m \le 100)$$$.
Next, $$$n$$$ lines follow. On the $$$i$$$-th of these lines, there is first a single integer $$$s_i$$$ and then there are $$$s_i$$$ integers that follow $$$(0 \le s_i \le m)$$$. The $$$j$$$-th of these integers on the $$$i$$$-th line, $$$a_{i,j}$$$, denotes that the $$$j$$$-th-from-the-bottom block on the $$$i$$$-th stack has the label $$$a_{i,j}$$$ in the final arrangement.
It is guaranteed that the number of blocks with a label $$$i$$$ is the same between the initial arrangement and final arrangement for all values of $$$i$$$.
First print a single number $$$k$$$, the number of moves in your sequence $$$(0 \le k \lt 2 \cdot 10^6)$$$. You do NOT have to minimize the number of moves in the sequence. It is provable that there always exists a solution in less than $$$2 \cdot 10^6$$$ moves given the specified input conditions.
Next, print $$$k$$$ lines. On the $$$i$$$-th line, print two numbers $$$x_i$$$ and $$$y_i$$$, denoting that on the $$$i$$$-th move, you will take a block from the top of stack $$$x_i$$$ and move it to the top of stack $$$y_i$$$. It must be the case that there exists at least one block on stack $$$x_i$$$ and less than $$$m$$$ blocks on stack $$$y_i$$$ before this move is made.
4 3 3 2 1 1 3 2 3 2 2 3 3 1 1
9 1 4 1 4 1 4 2 1 2 1 3 2 1 2 4 1 4 1
The following diagram shows the final arrangement of all the stacks from left to right.
Problem Credits: Eric Yachbes
Alex has an array $$$a_1,a_2,...,a_n$$$. A subarray $$$a_l, a_{l+1},...,a_r$$$ is good if both of the following are true:
- $$$r-l+1 \geq 2$$$
- $$$\max(a_l, a_{l+1},...,a_r)-\min(a_l, a_{l+1},...,a_r) \leq k$$$
In one operation, Alex can remove any good subarray $$$a_l, a_{l+1},...,a_r$$$ for a cost of $$$\lfloor \frac{r-l+1}{2} \rfloor$$$. He can perform the operation as many times as he likes (possibly zero times). Find the minimum size of the array that he can get as well as the minimum cost to obtain an array of minimum size.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 100)$$$. The description of the test cases follows.
The first line of each testcase contains $$$2$$$ integers, $$$n$$$ and $$$k$$$ $$$(1 \leq n \leq 500, 0 \leq k \leq 10^9)$$$.
The second line contains $$$n$$$ integers, $$$a_1, a_2,..., a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$.
For each test case output $$$2$$$ integers, the minimum size of the array that Alex can get followed by the minimum cost to obtain an array of minimum size.
56 01 1 5 5 1 16 41 1 5 5 1 16 14 3 3 1 1 610 23 5 3 6 4 2 2 3 3 81 01
0 3 0 2 1 2 0 4 1 0
In the first test case, the array is initially $$$[1, 1, 5, 5, 1, 1]$$$. Alex can remove subarray $$$[5, 5]$$$ for a cost of $$$1$$$ causing the array to become $$$[1, 1, 1, 1]$$$. He can then remove subarray $$$[1, 1, 1, 1]$$$ for a cost of $$$2$$$ causing the array to become empty.
In the second test case, the array is initially $$$[1, 1, 5, 5, 1, 1]$$$. Alex can remove subarray $$$[1, 1, 5]$$$ for a cost of $$$1$$$ causing the array to become $$$[5, 1, 1]$$$. He can then remove subarray $$$[5, 1, 1]$$$ for a cost of $$$1$$$ causing the array to become empty.
Problem Credits: Alex Liang and Larry Xing
Dustin has an array $$$a_1,a_2,\dots,a_n$$$ where each element is initially $$$0$$$ and is unmarked. The distance between the $$$i$$$-th element and the $$$j$$$-th element is $$$|i-j|$$$. He also has $$$q$$$ updates of two types:
- $$$1 \; i$$$ — toggle whether element $$$i$$$ is marked. Specifically, if element $$$i$$$ is unmarked, then mark it and if element $$$i$$$ is already marked, then unmark it.
- $$$2 \; k \; x$$$ — add $$$x$$$ to all elements that are a distance of at most $$$k$$$ from a marked element (note that if an element is a distance of at most $$$k$$$ from multiple marked elements, $$$x$$$ is only added to it once).
The first line contains $$$2$$$ integers, $$$n$$$ and $$$q$$$ ($$$1 \leq n$$$, $$$q \leq 10^5$$$).
Then $$$q$$$ lines follow, which describes the updates. Each line is given by one of the following formats:
- $$$1 \; i \;$$$ ($$$1 \leq i \leq n$$$) — an update of the first type
- $$$2 \; k \; x \;$$$ ($$$0 \leq k \leq n, \, 1 \leq x \leq 10^4$$$) — an update of the second type
Please output Dustin's array, $$$a_1,a_2,\dots,a_n$$$, after all updates are applied.
10 10 1 3 1 6 2 2 1 1 7 2 3 5 1 6 2 1 1 2 2 1 1 3 2 10 1
8 9 9 9 8 9 9 9 7 6
1 1 1 1
0
In the first test case, the array is of size $$$10$$$ and there are $$$10$$$ updates. The array after each update is shown below.
| $$$1 \; 3$$$ | $$$[0, 0, \color{red}{0}, 0, 0, 0, 0, 0, 0, 0]$$$ |
| $$$1 \; 6$$$ | $$$[0, 0, \color{red}{0}, 0, 0, \color{red}{0}, 0, 0, 0, 0]$$$ |
| $$$2 \; 2 \; 1$$$ | $$$[1, 1, \color{red}{1}, 1, 1, \color{red}{1}, 1, 1, 0, 0]$$$ |
| $$$1 \; 7$$$ | $$$[1, 1, \color{red}{1}, 1, 1, \color{red}{1}, \color{red}{1}, 1, 0, 0]$$$ |
| $$$2 \; 3 \; 5$$$ | $$$[6, 6, \color{red}{6}, 6, 6, \color{red}{6}, \color{red}{6}, 6, 5, 5]$$$ |
| $$$1 \; 6$$$ | $$$[6, 6, \color{red}{6}, 6, 6, 6, \color{red}{6}, 6, 5, 5]$$$ |
| $$$2 \; 1 \; 1$$$ | $$$[6, 7, \color{red}{7}, 7, 6, 7, \color{red}{7}, 7, 5, 5]$$$ |
| $$$2 \; 2 \; 1$$$ | $$$[7, 8, \color{red}{8}, 8, 7, 8, \color{red}{8}, 8, 6, 5]$$$ |
| $$$1 \; 3$$$ | $$$[7, 8, 8, 8, 7, 8, \color{red}{8}, 8, 6, 5]$$$ |
| $$$2 \; 10 \; 1$$$ | $$$[8, 9, 9, 9, 8, 9, \color{red}{9}, 9, 7, 6]$$$ |
Problem Credits: Alex Liang
Ariel is going on a vacation to cities $$$0 \dots n$$$ again! The cities are arranged in a row, with city $$$0$$$ on the left and city $$$n$$$ on the right. The cities from $$$1 \dots n$$$ all have some kind of cereal, denoted by integer $$$a_i$$$. Currently, Ariel is in city $$$0$$$ (there's no cereal in city $$$0$$$).
Each day, if Ariel is in city $$$k$$$, he will randomly (not necessarily uniformly) fly to any city from $$$k + 1 \dots n$$$ in such a way that he is $$$\frac{a_i}{a_j}$$$ times as likely to visit city $$$i$$$ compared to city $$$j$$$. Then, he buys a box of cereal from the city he arrives at.
However, some cities may be at war with each other (for example, they might disagree on whether milk or cereal goes first). If Ariel flies between two cities at war with each other, he will be deported and sent back to city $$$0$$$, and all his cereal boxes will be taken away. You will answer $$$q$$$ queries of the following form: if all cities from $$$l$$$ to $$$r$$$ are at war with each other, what is the expected number of cereal boxes Ariel will have when he reaches city $$$n$$$ modulo $$$10^9+7$$$? It is guaranteed none of the queries will involve city $$$n$$$
The problem has $$$t$$$ ($$$1 \leq t \leq 10^4$$$) independent test cases.
The first line of each test case contains two integers, $$$n$$$ and $$$q$$$ ($$$3 \leq n \leq 2 \cdot 10^5, 1 \leq q \leq 2 \cdot 10^5$$$). The next line contains $$$n$$$ integers, $$$a_1 \dots a_n$$$ ($$$1 \leq a_i \leq 5000$$$). $$$q$$$ lines follow, each containing two integers $$$l$$$ and $$$r$$$ ($$$1 \leq l \lt r \lt n$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot10^5$$$, and the sum of $$$q$$$ over all test cases also doesn't exceed $$$2 \cdot 10^5$$$.
For each test case, print $$$q$$$ integers; the $$$i$$$th integer should be the answer to the $$$i$$$th query modulo $$$10^9+7$$$.
Formally, let $$$M = 10^9 + 7$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod M$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output an integer $$$x$$$ such that $$$0 \leq x \lt M$$$ and $$$x \cdot q \equiv p \pmod M$$$.
23 11 2 31 24 21 1 1 12 31 3
464285719 450000005 882352949
The answer to the first query of the first test case is $$$\frac{41}{28}$$$.
Problem Credits: Anonymous Red Panda
Thomas is a very peculiar cereal farmer. He plants bushes of fruit-flavored cereal instead of trees like everyone else.
Thomas' farm is a rectangular grid size $$$n \times m$$$ ($$$1 \leq n,m \leq 64$$$). The rows are numbered $$$1\dots n$$$ from top to bottom and the columns are numbered $$$1 \dots m$$$ from left to right. Cell ($$$x$$$, $$$y$$$) is in row $$$x$$$ and column $$$y$$$. Some cells will be empty, and others he will plant a bush in, but he hasn't planted any yet.
Every morning Thomas will take a walk starting from cell ($$$1$$$, $$$1$$$) to cell ($$$n$$$, $$$m$$$). If he is currently in cell ($$$x$$$, $$$y$$$), he can only move to cell ($$$x + 1$$$, $$$y$$$) or cell ($$$x$$$, $$$y + 1$$$), and he must stay within the grid at all times. He can't move into cells that have a bush. It is possible that there is no valid path, or that he is unable to enter cell ($$$1$$$, $$$1$$$) due to there being a bush (in such a case there would also be no valid paths).
Please help Thomas first pick the dimensions of his grid, and then a way to plant bushes such that there are exactly $$$k$$$ different paths that Thomas can take on his morning walk. Two paths are considered different if there is a cell visited in one path but not the other. It can be shown that under the constraints of the problem this is always possible.
The first line contains $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases. Each test case will be one line that has an integer, $$$k$$$ ($$$0 \leq k \leq 10^{18}$$$).
Print the answer for each of the $$$t$$$ test cases.
In the first line, print two integers, $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 64$$$).
In the following line, print $$$x$$$, the number of bushes Thomas needs to plant. $$$x$$$ lines should come after, each containing two integers $$$r$$$ and $$$c$$$ , meaning Thomas should plant a bush in cell ($$$r$$$, $$$c$$$) ($$$1 \leq r \leq n, 1 \leq c \leq m$$$).
All the bushes should be distinct. If there are multiple valid solutions, print any.
215
1 1 0 3 3 1 1 3
In the first test case a $$$1 \times 1$$$ grid with no bushes has only one path in it satisfying the conditions.
For the second test case, without any bushes there are $$$5$$$ valid paths, but the bush in cell ($$$1$$$, $$$3$$$) blocks one of them, so there are only $$$4$$$ paths.
Problem Credits: Thomas Meeks
Ruby and Aqua are going to the amusement park!
The amusement park can be represented as a tree with $$$n$$$ nodes. Each node represents a ride with an enjoyment value of $$$a_i$$$ and an opening time of $$$b_i$$$. Ruby and Aqua can visit the rides by moving through the edges of the tree, and the first time they visit ride $$$i$$$, they will gain an enjoyment of $$$a_i$$$. However, the $$$i$$$-th ride is only open once every $$$b_i$$$ days. For example, if a ride has an opening time of $$$3$$$, then it will be open on days $$$3$$$, $$$6$$$, $$$9$$$, $$$\ldots$$$. If a ride is not open, all edges connected to the ride will be closed and no enjoyment can be gained from that ride.
However, Kana wants to interfere with Ruby and Aqua's plans, and she can choose to force any single ride to close. Ruby and Aqua want to figure out the maximum total enjoyment they can gain from visiting the amusement park even if Kana interferes, so they ask you $$$q$$$ queries of two types.
The $$$i$$$-th query contains three integers $$$x_i$$$, $$$y_i$$$, and $$$z_i$$$, asking if they visit the amusement park starting at node $$$x_i$$$ on day $$$y_i$$$ and Kana forcibly closes ride $$$z_i$$$, what is the maximum total enjoyment they can gain from exploring the park?
The first line contains two integers $$$n$$$ ($$$2 \le n \le 10^5$$$) and $$$q$$$ ($$$1 \le q \le 10^5$$$), denoting the size of the amusement park and the number of queries.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), denoting the enjoyment value of each ride.
The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^5$$$), denoting the opening time of each ride.
Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$), denoting an edge between ride $$$u$$$ and ride $$$v$$$. It is guaranteed that the given edges form a tree.
Each of the next $$$q$$$ lines contains three integers $$$x$$$ ($$$1 \le x \le n$$$), $$$y$$$ ($$$1 \le y \le 10^6$$$), and $$$z$$$ ($$$1 \le z \le n$$$), asking if Ruby and Aqua start at node $$$x$$$ on day $$$y$$$ and Kana forcibly closes ride $$$z$$$, what is the maximum total enjoyment they can gain from exploring the park.
Output $$$q$$$ lines each containing one integer. The $$$i$$$-th line should contain the answer to the $$$i$$$-th query.
7 6 1 2 3 4 5 6 7 3 1 4 6 3 7 5 1 2 2 3 2 4 2 5 1 6 6 7 1 123 2 2 124 1 7 7 1 7 5 7 4 1998 5 4 6 2
1 5 0 0 7 4
In the first query, rides $$$1$$$ and $$$2$$$ are open and reachable from node $$$1$$$. However, node $$$2$$$ is blocked, so the maximum total enjoyment the two can get is $$$a_1$$$ which is $$$1$$$.
In the second query, rides $$$1$$$, $$$2$$$, and $$$3$$$ are open and reachable from node $$$2$$$. However, node $$$1$$$ is blocked, so the maximum total enjoyment the two can get is $$$a_2 + a_3 $$$ which is $$$5$$$.
Problem Credits: Thomas Liu
Thomas owns a zoo filled with red pandas. The zoo can be described as a graph with $$$n$$$ nodes numbered $$$1 \dots n$$$ and $$$n-1$$$ bidirectional paths such that all pairs of nodes are connected through some series of paths.
Each node in this graph is either a feeding station or an exhibit. There are $$$k$$$ exhibits, and $$$n-k$$$ feeding stations. All nodes $$$i$$$ such that $$$1 \leq i \leq k$$$ are exhibits, while the rest of the nodes are feeding stations.
A feeding station at node $$$j$$$ ($$$k+1 \leq j \leq n$$$) contains cereal of color $$$c_j$$$, and when a red panda eats at this feeding station, its fur color becomes color $$$c_j$$$.
There are $$$m$$$ red pandas in this zoo, initially colored with color $$$0$$$ (which is red!). Red panda $$$p$$$ ($$$1 \leq p \leq m$$$) travels from node $$$a_p$$$ to node $$$b_p$$$ through the shortest series of paths, stopping at all feeding stations on the way to eat (including at $$$a_p$$$ and $$$b_p$$$).
For each of the $$$k$$$ exhibits, how many uniquely colored red pandas have been there? (including red pandas that start or end at the exhibit)
The first line contains two space separated integers $$$n$$$ and $$$k$$$ ($$$2 \leq k \leq n \leq 3 \cdot 10^5$$$).
The next line contains $$$n-k$$$ space separated integers. The $$$i$$$th integer represents color $$$c_{i+k}$$$, the color of the cereal of the feeding station at node $$$i + k$$$. ($$$1 \leq c_{i + k} \leq n$$$)
The next $$$n - 1$$$ lines contain two space separated integers $$$u_i$$$ and $$$v_i$$$, representing a path between nodes $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$). It is guaranteed that these paths form a tree.
The next line contains one integer $$$m$$$, representing the number of red pandas. ($$$1 \leq m \leq 3 \cdot 10^5$$$)
The next $$$m$$$ lines contains two space separated integers $$$a_j$$$ and $$$b_j$$$, the path of the $$$j$$$th red panda ($$$1 \leq a_j, b_j \leq n$$$).
Output $$$k$$$ lines, with the $$$i$$$th line containing one integer describing the number of uniquely colored red pandas that have crossed the exhibit at node $$$i$$$.
2 1 1 1 2 3 2 1 1 1 1 2
2
Two uniquely colored red pandas have been at node $$$1$$$. Red pandas $$$2$$$ and $$$3$$$ were color $$$0$$$ at node $$$1$$$, and red panda $$$1$$$ was color $$$1$$$ at node $$$1$$$.
Problem Credits: Eric Hsu
Larry, a cereal connoisseur, is traveling around the country CerealLand!
CerealLand consists of $$$n$$$ different cities, and Larry is currently at city $$$1$$$. Larry wants to purchase CerealLand's famed cereal.
At city $$$i$$$ ($$$1 \le i \le n$$$), you can buy a box of cereal for $$$c_i$$$ dollars.
There is a system of $$$n-1$$$ directed flights such that Larry can fly from city $$$1$$$ to any other city via a certain set of flights. Each flight has a cost, and the cost to fly flight $$$i$$$ ($$$1 \le i \le n-1$$$) is $$$b_i$$$.
However, each flight charges more for luggage, so to go on a flight Larry will also have to pay an additional $$$a_i \cdot x^2$$$ dollars, where $$$x$$$ is the number of cereal boxes Larry has purchased already.
Larry has $$$q$$$ queries for you, each query asking for the minimum amount of money it takes to go from city $$$1$$$ to city $$$v$$$ while purchasing $$$p$$$ boxes of cereal.
The first line of input contains two integers, $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2 \cdot 10^5$$$).
On the next line there are $$$n$$$ integers, $$$c_1$$$ ... $$$c_n$$$ ($$$1 \le c_i \le 10^9$$$).
The next $$$n-1$$$ lines contain information on the flights. The $$$i$$$-th line will have four integers, $$$u_i$$$, $$$v_i$$$, $$$a_i$$$, and $$$b_i$$$ ($$$1 \le u_i, v_i \le n, 1 \le a_i, b_i \le 10^9$$$), meaning there is a flight from city $$$u_i$$$ to city $$$v_i$$$ that costs $$$a_i \cdot x^2+b_i$$$ dollars, if $$$x$$$ is the number of cereal boxes Larry has already bought.
Finally the next $$$q$$$ lines describe the queries. Each query will take the form of two integers, $$$v$$$ and $$$p$$$ ($$$1 \le v \le n, 1 \le p \le 10^9$$$).
5 2 1 2 3 4 5 1 2 1 2 1 3 1 3 2 4 1 1 3 5 1 1 4 1 5 100
6 502
In the first query Larry can buy a box of cereal at city $$$1$$$, spending $$$1$$$ dollar. His flight to city $$$2$$$ will then cost $$$1 \cdot 1 + 2 = 3$$$ dollars, and his flight from city $$$2$$$ to city $$$4$$$ will cost $$$1 \cdot 1 + 1 = 2$$$ dollars, meaning he spends $$$6$$$ dollars total. It can be shown there is no better cost.
Problem Credits: Larry Xing