Roads and Gates の解説

ワープに対して超頂点を使えば終わり。 ワープのコスト計算のためにcostは2倍にしておく。

fn main() {
    input! {
        n: usize, m: usize, y: usize,
        uvt: [(Usize1, Usize1, usize); m],
        x: [usize; n]
    }
    let mut dist = vec![usize::MAX; n + 1];
    let mut to = vec![vec![]; n + 1];
    for &(u, v, t) in uvt.iter() {
        to[u].push((v, 2 * t));
        to[v].push((u, 2 * t));
    }
    for i in 0..n {
        to[i].push((n, 2 * x[i] + y));
        to[n].push((i, 2 * x[i] + y));
    }
    let mut heap = BinaryHeap::new();
    heap.push((Reverse(0), 0));
    let mut det = vec![false; n + 1];
    dist[0] = 0;
    while !heap.is_empty() {
        let (_, v) = heap.pop().unwrap();
        if det[v] {
            continue;
        }
        det[v] = true;
        for &(v2, cost) in to[v].iter() {
            if det[v2] {
                continue;
            }
            let nc = dist[v] + cost;
            if dist[v2] > nc {
                dist[v2] = nc;
                heap.push((Reverse(nc), v2));
            }
        }
    }
    let ans = dist[1..n].iter().map(|&e| e / 2).join(" ");
    println!("{}", ans);
}