Logo Universal Online Judge

UOJ

时间限制:5 s 空间限制:512 MB
Statistics

题目描述

给定一张 $n$ 个点,$m$ 条无向边,带边权的图,你需要找到一个边权最大的长度为 $k$ 的简单环。

你只需回答这个环的边权和,或报告无解。

输入格式

输入的第一行包括三个整数 $n,m,k$,含义如题目描述所述。

接下来 $m$ 行,每行三个整数 $x_i,y_i,w_i$ 描述一条无向边,保证没有重边与自环。

输出格式

如果图中存在长度为 $k$ 的简单环,则输出一行一个整数表示最大边权和。否则输出 -1

样例

见下发文件。

数据范围

对于所有数据,满足 $3 \le n,m,k \le 300, w_i\in[1,10^8]$。

Subtask $1$:保证 $n,m \le 10$。$20 \text{Pts}$。

Subtask $2$:保证 $n,m \le 50$。$30 \text{Pts}$

Subtask $3$:保证 $k= 6$。$ 30 \text{Pts}$。

Subtask $4$:无特殊限制。$20\text{Pts}$。

出题人: 注意到 $k\le 10$.

下发文件