問題一覧 > 通常問題

No.1898 Battle and Exchange

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (AC するまで非表示) / 解いたユーザー数 27
作問者 : Shirotsume / テスター : ygussany polylogK
お気に入りにしたユーザー ProblemId : 7427 / 自分の提出
問題文最終更新日: 2022-07-20 02:08:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 338 (順位表) の他の問題:

Problem Statement

There is a connected simple undirected graph with $N$ vertices and $M$ edges. Edge $i$ $(1 \leq i \leq M)$ connects vertices $U_i$ and $V_i$. A trial takes place on this graph.

On each vertex stands $1$ person. Each person holds $3$ cards, each with a positive integer written on it. The integers written on the cards held by the person at vertex $i$ $(1 \leq i \leq N)$ are $A_i, B_i, C_i$.

In addition to the $N$ people mentioned above, you, the challenger, are initially at vertex $1$. Like the others, you hold $3$ cards with positive integers written on them. The trial proceeds as follows.

  • Let $A_x, B_x, C_x$ be the integers written on the cards held by the person standing at your current vertex (hereafter called the opponent), and let $A', B', C'$ be the integers written on the cards you hold. If $A' + B' + C' > A_x + B_x + C_x$, you win; otherwise, you lose.
  • If you lose, the trial fails and ends. If you win, you may choose $1$ card each from the opponent's cards and your own cards and exchange them. You do not have to make the exchange. After that, choose any vertex adjacent to your current vertex and move to it. You may visit the same vertex multiple times during the trial.
  • Repeat the above at the vertex you moved to. The moment you defeat the person standing at vertex $N$, the trial succeeds and ends.

Note that no one other than you moves during the trial.

Let $A, B, C$ be the positive integers written on the cards you initially hold. Find $1$ combination of $A, B, C$ with which the trial can succeed and $A + B + C$ is minimized.

Constraints

  • All inputs are integers.
  • $2 \leq N \leq 10^5$
  • $\displaystyle N - 1 \leq M \leq \mathrm{min} \left(\frac{N(N - 1)}{2}, 10^5 \right)$
  • $1 \leq U_i, V_i \leq N$ $(1 \leq i \leq M)$
  • The given graph is connected and simple. (It has no multiple edges or self-loops.)
  • $1 \leq A_i, B_i, C_i \leq 10^8$ $(1 \leq i \leq N)$

Input

The input is given from standard input in the following format.
$N$ $M$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_{M}$ $V_{M}$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_N$ $B_N$ $C_N$

Output

Print $A, B, C$ with which the trial can succeed and $A + B + C$ is minimized, in the following format. If there are multiple possible combinations of $A, B, C$ as the answer, any of them will be accepted.

$A$ $B$ $C$
Print a newline at the end.

Sample

Sample 1
Input
4 3
4 3
3 2
1 3
4 3 3
5 4 2
5 4 1
9 9 4
Output
1 13 1

The graph and the cards initially held by the person at each vertex are shown in the figure below.

Here is an example of the procedure when $A = 1, B = 13, C = 1$. Below, a card with the integer $X$ written on it is simply called a $X$ card.

Initially, you are at vertex $1$. The person at vertex $1$ has the cards $4, 3, 3$, and since $4 + 3 + 3 < 1 + 13 + 1$, you win.

After winning, you exchange $1$ of your $1$ cards (here, $A$) for the $4$ card. After the exchange, $A = 4, B = 13, C = 1$.

Next, you move to vertex $3$, which is adjacent to vertex $1$. The person at vertex $3$ has the cards $5, 4, 1$, and since $5 + 4 + 1 < 4 + 13 + 1$, you win. You exchange your $1$ card for the opponent's $5$ card. After the exchange, $A = 4, B = 13, C = 5$.

Next, you move to vertex $2$, which is adjacent to vertex $3$. The person at vertex $2$ has the cards $5, 4, 2$, and since $5 + 4 + 2 < 4 + 13 + 5$, you win. You exchange the $4$ card for the $5$ card. Now $A = 5, B = 13, C = 5$.

Next, you return to vertex $3$ and defeat the person at vertex $3$. Since you exchanged cards during your previous visit to vertex $3$, the person at vertex $3$ now holds the cards $1, 4, 1$. You do not make an exchange here.

Finally, you move to vertex $4$. The person at vertex $4$ holds the cards $9, 9, 4$, and since $9 + 9 + 4 < 5 + 13 + 5$, you win. Since you have defeated the person at $N = 4$, the trial succeeds.

There is no way to make the trial succeed with $A + B + C < 15$. Therefore, this is a correct answer.

Answers such as 1 1 13 are also correct.

Sample 2
Input
3 2
1 2
2 3
1 1 1
1 1 1
100 100 100
Output
101 100 100

The graph and the cards initially held by the person at each vertex are shown in the figure below.

You do not have to make even $1$ exchange.

Sample 3
Input
4 4
1 2
1 3
2 4
3 4
1 3 5
2 2 2
2 3 4
3 4 5
Output
2 3 5

The graph and the cards initially held by the person at each vertex are shown in the figure below.

In this case, answers such as 1 4 5 and 2 4 4 are also correct.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。