結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー | aru aru |
提出日時 | 2020-12-15 22:01:30 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 269 ms / 2,000 ms |
コード長 | 3,110 bytes |
コンパイル時間 | 12,989 ms |
コンパイル使用メモリ | 214,900 KB |
実行使用メモリ | 29,112 KB |
最終ジャッジ日時 | 2023-10-20 06:46:59 |
合計ジャッジ時間 | 19,434 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 137 ms
16,408 KB |
testcase_03 | AC | 160 ms
29,052 KB |
testcase_04 | AC | 156 ms
28,968 KB |
testcase_05 | AC | 82 ms
29,016 KB |
testcase_06 | AC | 81 ms
29,016 KB |
testcase_07 | AC | 30 ms
9,904 KB |
testcase_08 | AC | 112 ms
22,740 KB |
testcase_09 | AC | 10 ms
5,528 KB |
testcase_10 | AC | 52 ms
14,196 KB |
testcase_11 | AC | 35 ms
9,940 KB |
testcase_12 | AC | 17 ms
7,984 KB |
testcase_13 | AC | 132 ms
20,716 KB |
testcase_14 | AC | 165 ms
24,920 KB |
testcase_15 | AC | 188 ms
26,988 KB |
testcase_16 | AC | 79 ms
16,508 KB |
testcase_17 | AC | 205 ms
29,112 KB |
testcase_18 | AC | 52 ms
12,308 KB |
testcase_19 | AC | 190 ms
26,964 KB |
testcase_20 | AC | 44 ms
9,972 KB |
testcase_21 | AC | 57 ms
14,480 KB |
testcase_22 | AC | 174 ms
24,888 KB |
testcase_23 | AC | 2 ms
4,348 KB |
testcase_24 | AC | 2 ms
4,348 KB |
testcase_25 | AC | 16 ms
7,896 KB |
testcase_26 | AC | 96 ms
16,408 KB |
testcase_27 | AC | 98 ms
16,448 KB |
testcase_28 | AC | 176 ms
24,932 KB |
testcase_29 | AC | 14 ms
7,888 KB |
testcase_30 | AC | 191 ms
26,960 KB |
testcase_31 | AC | 127 ms
18,556 KB |
testcase_32 | AC | 79 ms
14,260 KB |
testcase_33 | AC | 194 ms
29,048 KB |
testcase_34 | AC | 59 ms
12,288 KB |
testcase_35 | AC | 189 ms
26,964 KB |
testcase_36 | AC | 2 ms
4,348 KB |
testcase_37 | AC | 3 ms
4,348 KB |
testcase_38 | AC | 2 ms
4,348 KB |
testcase_39 | AC | 2 ms
4,348 KB |
testcase_40 | AC | 2 ms
4,348 KB |
testcase_41 | AC | 269 ms
27,032 KB |
testcase_42 | AC | 78 ms
10,048 KB |
testcase_43 | AC | 134 ms
16,364 KB |
testcase_44 | AC | 40 ms
7,856 KB |
testcase_45 | AC | 129 ms
16,376 KB |
testcase_46 | AC | 1 ms
4,348 KB |
testcase_47 | AC | 1 ms
4,348 KB |
ソースコード
package main import ( "bufio" "container/heap" "fmt" "math" "os" "sort" "strconv" ) var sc = bufio.NewScanner(os.Stdin) var wr = bufio.NewWriter(os.Stdout) func out(x ...interface{}) { fmt.Fprintln(wr, x...) } func getI() int { sc.Scan() i, e := strconv.Atoi(sc.Text()) if e != nil { panic(e) } return i } func getF() float64 { sc.Scan() i, e := strconv.ParseFloat(sc.Text(), 64) if e != nil { panic(e) } return i } func getInts(N int) []int { ret := make([]int, N) for i := 0; i < N; i++ { ret[i] = getI() } return ret } func getS() string { sc.Scan() return sc.Text() } // min, max, asub, absなど基本関数 func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b } // min for n entry func nmin(a ...int) int { ret := a[0] for _, e := range a { ret = min(ret, e) } return ret } // max for n entry func nmax(a ...int) int { ret := a[0] for _, e := range a { ret = max(ret, e) } return ret } func asub(a, b int) int { if a > b { return a - b } return b - a } func abs(a int) int { if a >= 0 { return a } return -a } func lowerBound(a []int, x int) int { idx := sort.Search(len(a), func(i int) bool { return a[i] >= x }) return idx } func upperBound(a []int, x int) int { idx := sort.Search(len(a), func(i int) bool { return a[i] > x }) return idx } //--------------------------------------------- // priority queue //--------------------------------------------- type pqi struct { a float64 to int } type priorityQueue []pqi func (pq priorityQueue) Len() int { return len(pq) } func (pq priorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] } func (pq priorityQueue) Less(i, j int) bool { return pq[i].a < pq[j].a } func (pq *priorityQueue) Push(x interface{}) { *pq = append(*pq, x.(pqi)) } func (pq *priorityQueue) Pop() interface{} { x := (*pq)[len(*pq)-1] *pq = (*pq)[0 : len(*pq)-1] return x } type edge struct { to int cost float64 } const inf = int(1e18) func main() { defer wr.Flush() sc.Split(bufio.ScanWords) sc.Buffer([]byte{}, 1000000) // this template is new version. // use getI(), getS(), getInts(), getF() N, M := getI(), getI() X, Y := getI()-1, getI()-1 p := make([]int, N) q := make([]int, N) for i := 0; i < N; i++ { p[i], q[i] = getI(), getI() } node := make([][]edge, N) for i := 0; i < M; i++ { from, to := getI()-1, getI()-1 dx := p[from] - p[to] dy := q[from] - q[to] dist := math.Sqrt(float64(dx*dx + dy*dy)) node[from] = append(node[from], edge{to, dist}) node[to] = append(node[to], edge{from, dist}) } dist := make([]float64, N) used := make([]bool, N) for i := 0; i < N; i++ { dist[i] = 1e18 } pq := priorityQueue{} heap.Push(&pq, pqi{0, X}) dist[X] = 0 for len(pq) != 0 { cur := pq[0].to heap.Pop(&pq) if used[cur] { continue } used[cur] = true for _, e := range node[cur] { if dist[e.to] > dist[cur]+e.cost { dist[e.to] = dist[cur] + e.cost heap.Push(&pq, pqi{dist[e.to], e.to}) } } } // out(dist) out(dist[Y]) }