问题 5042 -- 困难游走

5042: 困难游走

题目描述

  给你 $n$ 个结点的有向图,编号 $0$ 到 $n-1$。
每条边都有一个价值,当你经过某条边时,你的总得分就增加该价值,如果你重复经过某条边多次,那么边的价值就多次加进你的总得分,每条边的价值范围是:$[-499,499]$。
这个有向图没有自环(则没有结点有边自己指向自己)。你刚开始在 $0$ 号结点,你想走到结点 $1$,而且它要在整数区间 $[1,\mathrm{timeLimit}]$ 秒内到达。你每秒必须严格走 $\mathrm{stepsPerSecord}$ 步(每走一条边称为一步),你的目标是得到最高分。

输入

多组测试数据。
第一行,一个整数 $R$,表示有 $R$ 组测试数据。
每组测试数据格式如下:
第一行,三个正整数分别是:$n,\mathrm{stepsPerSecond},\mathrm{timeLimit}$。
接下来有 $n$ 行 $n$ 列的邻接矩阵。如果第 $i$ 行第 $j$ 列的值是 $1000$,表示结点 $i$ 到结点 $j$ 没有边,否则表示结点 $i$ 到结点 $j$ 有一条有向边,价值是该数。

输出

共 $R$ 行,每行一个整数,蚂蚁能得到的最高分,如果无法到达目标,则输出 IMPOSSIBLE。

样例输入输出

输入#1 复制
2
2 3 2
1000 1
1 1000
4 7 9
1000 1 1 1000
1000 1000 1000 1000
1000 1000 1000 1
1 1000 1000 1000
输出#1 复制
3
49
输入#2 复制
4
2 1 9
1000 -4
-8 1000
4 5 777
1000 23 66 98
89 1000 35 64
23 78 1000 88
78 19 57 1000
4 1 19260817
1000 -63 28 64
37 1000 -74 97
72 -49 1000 54
72 95 -75 1000
4 67 998244353
1000 1000 -19 1000
55 1000 84 -53
57 89 1000 85
78 -39 68 1000
输出#2 复制
-4
341849
1849038321
5785325147593

提示

对于 $10\%$ 的数据,$\mathrm{stepsPerSecond}=1 ,\  1 \leq \mathrm{timeLimit} \leq 1000, \ n=2$;
另有 $20\%$ 的数据,$ 1 \leq \mathrm{timeLimit} \leq 1000$;
另有 $20\%$ 的数据,$ \mathrm{stepsPerSecond}=1$;
对于 $100\%$ 的数据:$1\leq R \leq 11$ , $1 \leq \mathrm{timeLimit} \leq 10^9$, $\mathrm{stepsPerSecond} \leq 100$, $1 \leq n \leq 50$。

序号 标题 作者 发表时间 费用 订购数 操作