AtCoder Beginner Contest 445 F

https://atcoder.jp/contests/abc445/tasks/abc445_f

回のの最短距離をとすると、回のの最短距離は、

となります。
行列を掛け算と同じように転置してみましたが、変わらないですね。N=1024だと2倍速かったです。

// Exactly K Steps 2
#![allow(non_snake_case)]

use std::cmp::min;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// Matrix ////////////////////

type Matrix = Vec<Vec<i64>>;

fn read_matrix(N: usize) -> Matrix {
    (0..N).map(|_| read_vec::<i64>()).collect::<Matrix>()
}

fn transpose(A: &Matrix) -> Matrix {
    let N = A.len();
    let mut B: Matrix = vec![vec![0; N]; N];
    for i in 0..N {
        for j in 0..N {
            B[i][j] = A[j][i]
        }
    }
    B
}

fn mul(A: &Matrix, B: &Matrix) -> Matrix {
    let N = A.len();
    let tB = transpose(B);
    let mut C: Matrix = vec![vec![i64::MAX; N]; N];
    for i in 0..N {
        for j in 0..N {
            for k in 0..N {
                C[i][j] = min(A[i][k] + tB[j][k], C[i][j])
            }
        }
    }
    C
}

fn pow(A: &Matrix, e: usize) -> Matrix {
    if e == 1 {
        A.clone()
    }
    else if e % 2 == 1 {
        mul(A, &pow(A, e-1))
    }
    else {
        let B = pow(A, e/2);
        mul(&B, &B)
    }
}


//////////////////// process ////////////////////

fn read_input() -> (usize, Matrix) {
    let v: Vec<usize> = read_vec();
    let (N, K) = (v[0], v[1]);
    let C = read_matrix(N);
    (K, C)
}

fn F(K: usize, C: Matrix) {
    let N = C.len();
    let A = pow(&C, K);
    for s in 0..N {
        println!("{}", A[s][s])
    }
}

fn main() {
    let (K, C) = read_input();
    F(K, C)
}