問題一覧 > 通常問題

No.3668 Minimum Cut

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 12
作問者 : 👑 みうね / テスター : harurun TKTYI
お気に入りにしたユーザー ProblemId : 13414 / 自分の提出
問題文最終更新日: 2026-09-03 22:46:13
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 512 BONSAI (順位表) の他の問題:

Problem Statement

You are given a directed graph with $N$ vertices and $M$ edges. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $M$. This graph may contain multiple edges, but it contains no self-loops.

Edge $i$ goes from vertex $u_i$ to vertex $v_i$, and deleting this edge costs $c_i$.

You delete $0$ or more edges so that vertex $T$ becomes unreachable from vertex $S$. Find the minimum possible total cost of the deleted edges.

Input

The input is given from standard input in the following format. 

$N\ M\ S\ T$
$u_1\ v_1\ c_1$
$u_2\ v_2\ c_2$
$\vdots$
$u_M\ v_M\ c_M$

Constraints

  • $2 \leq N \leq 2000$
  • $1 \leq M \leq 10000$
  • $1 \leq S,T \leq N$
  • $S \neq T$
  • $1 \leq u_i,v_i \leq N$
  • $u_i \neq v_i$
  • $1 \leq c_i \leq 10^9$
  • All input values are integers.

Output

Output the minimum total cost required to make vertex $T$ unreachable from vertex $S$.

Print a newline at the end of the output.

Sample

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

One way is to delete both of the $2$ edges leaving vertex $1$, and its cost is $5$.

Sample 2
Input
3 5 1 3
1 2 4
1 2 7
2 3 20
1 3 3
3 1 100
Output
14

First, the edge going directly from vertex $1$ to vertex $3$ must be deleted, which costs $3$. Furthermore, to cut the path from vertex $1$ via vertex $2$, you must either delete both of the $2$ edges going from vertex $1$ to vertex $2$, or delete the edge going from vertex $2$ to vertex $3$. The former costs $4+7=11$ and the latter costs $20$, so we choose the former. Therefore, the minimum total cost required is $3+11=14$.

Sample 3
Input
5 4 2 5
2 1 8
1 3 4
4 5 9
5 4 2
Output
0

Vertex $5$ is already unreachable from vertex $2$ from the start, so no edges need to be deleted.

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