AtCoder ABC 143 E - Travel by Car (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。コンテストに出る習慣をどうにか取り戻したいところです。

問題

難しいアルゴリズムが求められそうですが、実装力があれば解けてしまう問題です。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextStr() string {
    sc.Scan()
    return sc.Text()
}

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

const INF = 10000000000

type info struct {
    supply int
    fuel   int
}

type infoes []info

func less(info1, info2 info) bool {
    if info1.supply != info2.supply {
        return info1.supply < info2.supply
    }
    return info1.fuel >= info2.fuel
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Buffer(make([]byte, 0), 1000000001*3)
    sc.Split(bufio.ScanWords)
    n, m, l := nextInt(), nextInt(), nextInt()
    adj := make([][]int, n)
    for i := range adj {
        adj[i] = make([]int, n)
        for j := range adj[i] {
            if i != j {
                adj[i][j] = INF
            }
        }
    }
    for k := 0; k < m; k++ {
        a, b, c := nextInt(), nextInt(), nextInt()
        if c <= l {
            adj[a-1][b-1], adj[b-1][a-1] = c, c
        }
    }

    dist := make([]infoes, n)
    for i := range dist {
        dist[i] = make(infoes, n)
        dist[i][i] = info{0, l}
        for j := range dist[i] {
            if i != j {
                dist[i][j] = info{INF, 0}
            }
        }
        remain := make(map[int]struct{})
        for j := 0; j < n; j++ {
            remain[j] = struct{}{}
        }
        for len(remain) > 0 {
            u := -1
            for k := range remain {
                if u == -1 || less(dist[i][k], dist[i][u]) {
                    u = k
                }
            }
            delete(remain, u)
            for v, a := range adj[u] {
                if a > l {
                    continue
                }
                next := dist[i][u]
                if next.fuel < a {
                    next.supply++
                    next.fuel = l
                }
                next.fuel -= a
                if less(next, dist[i][v]) {
                    dist[i][v] = next
                }
            }
        }
    }

    q := nextInt()
    for p := 0; p < q; p++ {
        s, t := nextInt(), nextInt()
        ans := dist[s-1][t-1].supply
        switch {
        case ans == INF:
            fmt.Println(-1)
        default:
            fmt.Println(ans)
        }
    }
}

ある町を始点としたときに各町への最短距離をどのように表せばよいか考えてみます。このとき補給回数と燃料タンクの残量とのセットを距離として用いるのがよさそうです。すると、ある町から各町へ向かうときの補給回数の最小値がダイクストラ法により求められます。あとはすべての町を始点にしてダイクストラ法をそれぞれ適用すれば任意の2つの町の組み合わせについて補給回数の最小値が求められます。

ダイクストラ法1回の計算量は道の数が $O(N^2)$ なので優先度付きキューを使おうと使うまいと $O(N^2)$ になります。 $Q$ が $O(N^2)$ であることを考慮すると、全体の計算量は $O(N^3)$ となります。