Warshall Floyd
(graph/warshall-floyd/src/lib.rs)

• View this file on GitHub
• Last update: 2025-05-26 22:58:00+09:00

Description

Verified with

• verification/aizu-online-judge/grl_1_c/src/main.rs

Code

#[derive(Debug, Clone, Copy)]
pub struct Edge {
    from: usize,
    to: usize,
    cost: i64,
}

impl Edge {
    pub fn new(from: usize, to: usize, cost: i64) -> Self {
        Self { from, to, cost }
    }
}

#[derive(Debug, Clone)]
pub struct WarshallFloyd {
    size: usize,
    edge: Vec<Edge>,
}

impl WarshallFloyd {
    pub fn new(size: usize) -> Self {
        Self { size, edge: vec![] }
    }

    pub fn add_edge(&mut self, from: usize, to: usize, cost: i64) {
        self.edge.push(Edge::new(from, to, cost));
    }

    pub fn warshall_floyd(&mut self) -> (bool, Vec<Vec<i64>>) {
        let mut dist = vec![vec![i64::MAX / 4; self.size]; self.size];
        for i in 0..self.size {
            dist[i][i] = 0;
        }
        for edge in &self.edge {
            dist[edge.from][edge.to] = edge.cost;
        }
        for k in 0..self.size {
            for i in 0..self.size {
                for j in 0..self.size {
                    dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j])
                }
            }
        }
        for i in 0..self.size {
            if dist[i][i] < 0 {
                return (true, dist);
            }
        }
        (false, dist)
    }
}

pub fn warshall_floyd(size: usize, edge: &Vec<(usize, usize, i64)>) -> (bool, Vec<Vec<i64>>) {
    let mut dist = vec![vec![i64::MAX / 4; size]; size];
    for i in 0..size {
        dist[i][i] = 0;
    }
    for &(from, to, cost) in edge {
        dist[from][to] = cost;
    }
    for k in 0..size {
        for i in 0..size {
            for j in 0..size {
                dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j])
            }
        }
    }
    let mut cycle = false;
    for i in 0..size {
        if dist[i][i] < 0 {
            cycle = true;
        }
    }
    (cycle, dist)
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page