题意
加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。这个可乐机器人有三种行为：停在原地、去下一个相邻的城市。自爆。它每一秒都会随机触发一种行为。现在给出加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市，问经过了 $t$ 秒，可乐机器人的行为方案数是多少？
一共有 $n$ 个点，$m$ 条边。
$1 \leq n \leq 30, 1 \leq m \leq 100, 1 \leq t \leq 10^6$
题解
邻接矩阵自乘即可。
停在原地表示为自环。
自爆表示为走向哨兵节点。
矩阵的 $t$ 次幂的第一行的和即为答案。
时间复杂度 $\Theta \left(n^3 \log t\right)$