AtCoder Beginner Contest 317 C - Remembering the Days

## 問題

atcoder.jp

考察

この問題はどうやって解くのだろう。。。とモヤモヤ悩んでいる間に時間切れ。。。

解答を見ると、DFS（深さ優先探索）で導き出すのが良いとのこと。

とりあえず、Goで書いている人の解答例を見て学ぶことにする。

DFSを行うにあたり、どのようなデータを作るのが良いかを見てみるのだが、やはりmapにするのが良さそうだ。

頂点と辺の関係を以下のようなデータ（頂点に対して隣接する頂点と辺（距離）で表すデータ）にしておくのがわかり易い。

map[1:[{2 1} {3 100} {4 1000}] 2:[{1 1} {3 10}] 3:[{2 10} {1 100}] 4:[{1 1000}]]

あとは、問題文の「好きな街からスタートして同じ街を二度以上通らずに別の街へ移動するときの、通る道路の長さの和としてありえる最大値を求めてください。」に注意する。

つまり、すべての街を通らなくても良く、とにかく最大値を求めれば良いということ。

そうなると以下解答で納得がいく。まだまだ勉強不足。。。

解答

package main

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

type Town struct {
    town int
    road int
}

var maxDistance int
var visited []bool

func dfs(graph map[int][]Town, current int, distance int) {
    if distance > maxDistance {
        maxDistance = distance
    }
    visited[current] = true

    for _, Town := range graph[current] {
        if !visited[Town.town] {
            dfs(graph, Town.town, distance+Town.road)
        }
    }

    visited[current] = false
}

func main() {
    in := bufio.NewReader(os.Stdin)
    out := bufio.NewWriter(os.Stdout)
    defer out.Flush()

    var N, M int
    fmt.Fscan(in, &N, &M)

    x := make(map[int][]Town)
    for i := 0; i < M; i++ {
        var A, B, C int
        fmt.Fscan(in, &A, &B, &C)
        x[A] = append(x[A], Town{town: B, road: C})
        x[B] = append(x[B], Town{town: A, road: C})
    }

    maxDistance = 0
    visited = make([]bool, N+1)

    for i := 1; i <= N; i++ {
        dfs(x, i, 0)
    }

    fmt.Fprintln(out, maxDistance)
}