fn dijkstra(edges: Vec<Vec<[usize; 2]>>, num_v: usize) -> Vec<usize>{
let inf = 999;
let mut dist = Vec::new();
for _ in 0..num_v {
dist.push(inf);
}
dist[0] = 0;
let mut q = Vec::new();
for i in 0..num_v {
q.push(i);
}
while *&q.len() > 0 {
let mut r = q[0];
for i in &q{
if dist[*i] < dist[r] {
r = *i;
}
}
let n = q.iter().position(|n| *n == r).unwrap();
let u = q[n];
q.retain(|&x| x != u);
for i in edges[u].clone() {
if dist[i[0]] > dist[u] + i[1] {
dist[i[0]] = dist[u] + i[1];
}
}
}
return dist;
}
fn main() {
let edges = vec![
vec![[1, 4], [2, 3]],
vec![[2, 1], [3, 1], [4, 5]],
vec![[5, 2]],
vec![[4, 3]],
vec![[6, 2]],
vec![[4, 1], [6, 4]],
vec![],
];
println!("{:?}", edges);
println!("{:?}", dijkstra(edges, 7));
}
Compiling rust v0.1.0 (/home/vagrant/dev/algorithm/rust)
Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.24s
Running `target/debug/rust`
[[[1, 4], [2, 3]], [[2, 1], [3, 1], [4, 5]], [[5, 2]], [[4, 3]], [[6, 2]], [[4, 1], [6, 4]], []]
[0, 4, 3, 5, 6, 5, 8]
おおおお、これは凄いな…