ノード間の最短距離を計算します。
DPの一つ
$O(n^3)$
無向グラフ
use std::cmp::{max, min};
fn all_shortest_paths(mut d: Vec<Vec<Vec<i64>>>, n: usize) {
for k in 0..n {
for i in 0..n {
for j in i+1..n {
d[k+1][i][j] = min(
d[k][min(i, k)][max(i, k)] + d[k][min(k, j)][max(k, j)],
d[k][i][j]);
}
}
for i in 0..n {
println!("{:?}", d[k+1][i]);
}
println!();
}
}
fn main() {
let inf = i64::max_value() / 2;
// 初期化
let n = 5;
let mut d = vec![vec![vec![0; n]; n]; n+1];
d[0][0][1] = 1;
d[0][0][2] = 2;
d[0][0][3] = inf;
d[0][0][4] = inf;
d[0][1][2] = 5;
d[0][1][3] = 1;
d[0][1][4] = inf;
d[0][2][3] = 4;
d[0][2][4] = 2;
d[0][3][4] = 1;
for i in 0..n {
println!("{:?}", d[0][i]);
}
println!();
all_shortest_paths(d, n);
}
隣接行列の片側も使う場合
より簡単にかけます。
use std::cmp::min;
// // https://atcoder.jp/contests/abc021/submissions/5777748
// ↓
use std::io::prelude::*;
fn input<T>() -> T
where T: std::str::FromStr {
let stdin = std::io::stdin();
let token: String = stdin
.lock()
.bytes()
.map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().unwrap()
}
// ↑
// // https://atcoder.jp/contests/abc021/submissions/5777748
static INF: i64 = 100_000_000;
fn main() {
let n = input::<usize>(); // ノード数
let m = input::<usize>(); // パス数
let v = (0..m) // パス (ノードa, ノードb, パス(a, b)のコスト)
.map(|_| (input::<usize>()-1, input::<usize>()-1, input()))
.collect::<Vec<(_, _, i64)>>();
let mut d = vec![vec![INF; 100]; 100];
for i in 0..n {
d[i][i] = 0;
}
for &(a, b, c) in &v {
d[a][b] = min(d[a][b], c);
d[b][a] = min(d[b][a], c);
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
d[i][j]=min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for &(a, b, c) in &v {
println!("({}, {}) において {} -> {}",a+1, b+1, c, d[a][b]);
}
}
3 3
1 2 1
1 3 1
2 3 3
(1, 2) において 1 -> 1
(1, 3) において 1 -> 1
(2, 3) において 3 -> 2
最短パスとして使われるパスの数
AtCoder にて２回程見たことがあります。
#![allow(unused_imports)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(dead_code)]
#![allow(unused_variables)]
use std::collections::HashSet;
use std::collections::HashMap;
use std::collections::BTreeSet;
use std::collections::VecDeque;
use std::cmp::{max, min};
use std::mem::swap;
use std::io::prelude::*; // input()
fn input<T>() -> T
where T: std::str::FromStr {
let stdin = std::io::stdin();
let token: String = stdin
.lock()
.bytes()
.map(|c| c.unwrap() as char)
.skip_while(|c| c.is_whitespace())
.take_while(|c| !c.is_whitespace())
.collect();
token.parse().ok().unwrap()
}
static INF: usize = 1_000_000;
fn main() {
let n = input::<usize>();
let m = input::<usize>();
let abc = (0..m)
.map(|_| (input::<usize>()-1,input::<usize>()-1,input::<usize>()))
.collect::<Vec<_>>();
let mut d = vec![vec![INF; 100]; 100];
for i in 0..n {
d[i][i] = 0;
}
for &(a, b, c) in &abc {
d[a][b] = min(d[a][b], c);
d[b][a] = min(d[b][a], c);
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
// 追加分
let mut ans = m;
for &(a, b, c) in &abc {
let shortest = || {
for j in 0..n {
if d[j][a] + c == d[j][b] {
return true;
}
}
false
};
if shortest() {
ans-=1;
}
}
println!("{}", ans);
// 追加分
}