問題一覧 > 通常問題

No.1320 Two Type Min Cost Cycle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 81
作問者 : ningenMe / テスター : maspy
お気に入りにしたユーザー ProblemId : 5567 / 自分の提出
問題文最終更新日: 2020-12-16 02:10: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
Advent Calendar Contest 2020 (順位表) の他の問題:

Problem Statement

You are given an integer $T$ and a weighted graph with $N$ vertices and $M$ edges.
In this graph, there is at most $1$ edge connecting the same pair of $2$ vertices. Also, this graph has no edge whose two endpoints are the same vertex.


$T$ is either $0$ or $1$.

  • When $T=0$

    The given graph is an undirected graph. The $i$-th edge connects vertices $u_i$ and $v_i$ bidirectionally with weight $w_i$.

  • When $T=1$

    The given graph is a directed graph. The $i$-th edge goes from vertex $u_i$ to vertex $v_i$ with weight $w_i$.


Find the minimum size of a cycle contained in the given graph. The size of a cycle is the sum of the weights of the edges it contains. If no cycle exists, output -1.

Notes

  • For the definition of a cycle, refer to the description of cycle graph.
  • Due to the time limit, Python users are recommended to submit with PyPy.

Input

$T$
$N\ M$
$u_1\ v_1\ w_1$
$\vdots$
$u_M\ v_M\ w_M$
  • All inputs are integers
  • $0 \le T \le 1$
  • $1 \le N \le 2000$
  • $0 \le M \le \min( 2000, N(N-1)/2) $
  • $1 \le u_i \le N$
  • $1 \le v_i \le N$
  • $1 \le w_i \le 10^9$
  • $u_i \neq v_i $
  • $(u_i,v_i) \neq (u_j,v_j) \ (i \neq j) $
  • $(u_i,v_i) \neq (v_j,u_j) \ (i \neq j) $

Output

Find the minimum size of a cycle contained in the given graph. If no cycle exists, output -1.

Print a newline at the end.

Sample

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

The route visiting the vertices in the order $(1,2,3,1)$ is one of the minimum cycles.

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

The route visiting the vertices in the order $(1,2,4,1)$ is one of the minimum cycles.

Sample 3
Input
0
3 1
1 2 1
Output
-1

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