#337228 (Go) No.92 逃走経路

• 問題: No.92 逃走経路
• ユーザー: tsuchinaga
• 提出日時: 2019-04-12 13:43:23
• 言語: Go (1.23.4)
• 結果: AC
• 実行時間: 51 ms / 5,000 ms
• コード長: 1,724 bytes
• コンパイル時間: 14,117 ms
• コンパイル使用メモリ: 241,756 KB
• 実行使用メモリ: 7,900 KB
• 最終ジャッジ日時: 2024-09-14 01:07:27
• 合計ジャッジ時間: 15,463 ms
• ジャッジサーバーID （参考情報）: judge6 / judge2

ファイルパターン	結果
sample	AC * 2
other	AC * 18

ソースコード

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package main
import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
)
func main() {
    sc := bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    sc.Scan()
    n, _ := strconv.Atoi(sc.Text())
    sc.Scan()
    m, _ := strconv.Atoi(sc.Text())
    sc.Scan()
    k, _ := strconv.Atoi(sc.Text())
    // 犯人が潜伏しうる町
    cities := make([]int, n)
    for i := range cities {
        cities[i] = i + 1
    }
    // fmt.Println(cities)
    // どこからどこにいくのにいくらかかるか
    type route struct {
        to, cost int
    }
    routes := make(map[int][]route)
    for i := 0; i < m; i++ {
        sc.Scan()
        a, _ := strconv.Atoi(sc.Text())
        sc.Scan()
        b, _ := strconv.Atoi(sc.Text())
        sc.Scan()
        c, _ := strconv.Atoi(sc.Text())
        if _, ok := routes[a]; !ok {
            routes[a] = make([]route, 0)
        }
        routes[a] = append(routes[a], route{b, c})
        if _, ok := routes[b]; !ok {
            routes[b] = make([]route, 0)
        }
        routes[b] = append(routes[b], route{a, c})
    }
    // fmt.Println(routes)
    for i := 0; i < k; i++ {
        sc.Scan()
        c, _ := strconv.Atoi(sc.Text())
        exists := make(map[int]int) // キーが町
        for _, city := range cities {
            // cityから行けるところで、cの通行料金がかかるところがあるか
            if len(routes[city]) > 0 {
                for _, r := range routes[city] {
                    if r.cost == c {
                        exists[r.to]++
                    }
                }
            }
        }
        // fmt.Println(i, "exists", exists)
        cities = make([]int, len(exists))
        i := 0
        for e := range exists {
            cities[i] = e
            i++
        }
        // fmt.Println(i, "cities", cities)
    }
    sort.Slice(cities, func(i, j int) bool {
        return cities[i] < cities[j]
    })
    s := ""
    for _, c := range cities {
        if s != "" {
            s += " "
        }
        s += strconv.Itoa(c)
    }
    fmt.Println(len(cities))
    fmt.Println(s)
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX