题目描述
给定一张 $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$.