1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
use std::{
cmp::Reverse,
collections::BinaryHeap,
io::{stdin, Read},
usize,
};
fn diff(a: usize, b: usize) -> usize {
a.max(b) - a.min(b)
}
fn main() {
let mut input = String::new();
stdin().lock().read_to_string(&mut input).unwrap();
let mut ints = input
.split_ascii_whitespace()
.map(|i| i.parse::<usize>().unwrap());
let mut get = || ints.next().unwrap();
for case in 1..=get() {
let (n, p) = (get(), get());
let xs = (0..n)
.map(|_| {
let (mut min, mut max) = (usize::MAX, 0);
for _ in 0..p {
let x = get();
min = min.min(x);
max = max.max(x);
}
(min, max)
})
.collect::<Vec<(_, _)>>();
let mut q = BinaryHeap::new();
q.push((Reverse(0), 0, 0));
while let Some((Reverse(dist), i, v)) = q.pop() {
// eprintln!("dist = {}; i = {}; v = {}", dist, i, v);
if i == n {
println!("Case #{}: {}", case, dist);
break;
}
let (min, max) = xs[i];
let dist_a = dist + diff(v, min) + diff(min, max);
q.push((Reverse(dist_a), i + 1, max));
let dist_b = dist + diff(v, max) + diff(max, min);
q.push((Reverse(dist_b), i + 1, min));
}
}
}
|
