Wheel Distance の解説

s -> tの最短経路として次の2つが考えられる。 これらの最小値を取ればOK

頂点n + 1を通る経路

これは頂点n + 1からの最短経路distをdijkstraで求めることで

dist[s] + dist[t]にて計算可能。

頂点n + 1を通らない経路

s -> tに時計回り or 反時計回りで回っていく方法のうち小さい方が答え。 これはAの累積和を求めておくことで計算可能。

dijkstraと累積和を事前に計算しておけば各クエリにO(1)で答えられてとても嬉しい。

fn main() {
    input! {
        n: usize, q: usize,
        a: [usize; n],
        b: [usize; n],
        st: [(Usize1, Usize1); q]
    }
    let pref = PrefixSum1D::new(&a);
    let to = {
        let mut to = vec![vec![]; n + 1];
        for i in 0..n {
            let now = i;
            let next = (i + 1) % n;
            to[now].push((next, a[i]));
            to[next].push((now, a[i]));
        }
        for i in 0..n {
            to[i].push((n, b[i]));
            to[n].push((i, b[i]));
        }
        to
    };
    let dist = {
        let mut dist = vec![usize::MAX; n + 1];
        let mut heap = BinaryHeap::new();
        heap.push((Reverse(0), n));
        dist[n] = 0;
        let mut det = vec![false; n + 1];
        while !heap.is_empty() {
            let (_, v) = heap.pop().unwrap();
            if det[v] {
                continue;
            }
            det[v] = true;
            for &(v2, c) in to[v].iter() {
                if det[v2] {
                    continue;
                }
                let nc = dist[v] + c;
                if dist[v2] > nc {
                    dist[v2] = nc;
                    heap.push((Reverse(nc), v2));
                }
            }
        }
        dist
    };
    let ans = st
        .iter()
        .map(|&(s, t)| {
            let ans1 = dist[s] + dist[t];
            let ans2 = if t == n {
                ans1
            } else {
                let right = pref.range_sum(s..=t - 1);
                let left1 = if s == 0 { 0 } else { pref.range_sum(..=s - 1) };
                let left2 = pref.range_sum(t..);
                min(left1 + left2, right)
            };
            min(ans1, ans2)
        })
        .join("\n");
    println!("{}", ans);
}