问题 K: Circuit

内存限制：256 MB 时间限制：5 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：5 通过：2

Now there is a directed graph

G = (V, E)

with

n

vertices and

m

edges (the graph does not guarantee connectivity). You need to calculate the length of the circuit with the smallest length. At the same time, on this basis you also need to count the number of the circuit with the smallest length. There are no multiedges and self-loops in the graph.

The first line of input is a positive integer $T (T \leq 15)$ representing the number of test cases. Description of the test cases follows:

The first line of each test case contains two integers $n$ and $m$ $(1 \leq n \leq 500, 0 \leq m \leq n \times (n - 1))$ —— the number of the vertices and edges in the given graph.

Each of the next $m$ lines contains two integers $u_{i}$ , $v_{i}$ and $w_{i}$ $(1 \leq u_{i}, v_{i} \leq n, 1 \leq w_{i} \leq 1 0^9)$ meaning that there is a directed edge of length $w_{i}$ between vertex $u_{i}$ and vertex $v_{i}$ in the graph.

The data guarantees that there will be no more than $10$ groups with a value of $n$ exceeding .

For each case, output two integers representing the length and the number of the circuit with the smallest length. Since the number may be large, you need to output the result of modulating the answer to

998244353

.Output -1 -1 if there is no circuit.

7 2
-1 -1
8 4

问题 K: Circuit

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

问题 K: Circuit

题目描述

输入格式

输出格式

输入样例 复制

输出样例 复制

输入样例复制

输出样例复制