結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー |
![]() |
提出日時 | 2020-12-16 20:48:27 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 224 ms / 2,000 ms |
コード長 | 3,110 bytes |
コンパイル時間 | 15,422 ms |
コンパイル使用メモリ | 218,812 KB |
実行使用メモリ | 29,312 KB |
最終ジャッジ日時 | 2024-09-20 05:19:28 |
合計ジャッジ時間 | 22,405 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,816 KB |
testcase_01 | AC | 1 ms
6,940 KB |
testcase_02 | AC | 99 ms
14,104 KB |
testcase_03 | AC | 153 ms
25,088 KB |
testcase_04 | AC | 151 ms
27,392 KB |
testcase_05 | AC | 88 ms
29,312 KB |
testcase_06 | AC | 83 ms
26,536 KB |
testcase_07 | AC | 30 ms
7,808 KB |
testcase_08 | AC | 114 ms
20,736 KB |
testcase_09 | AC | 9 ms
5,376 KB |
testcase_10 | AC | 52 ms
11,776 KB |
testcase_11 | AC | 34 ms
8,960 KB |
testcase_12 | AC | 16 ms
6,528 KB |
testcase_13 | AC | 120 ms
20,736 KB |
testcase_14 | AC | 137 ms
23,168 KB |
testcase_15 | AC | 172 ms
26,880 KB |
testcase_16 | AC | 71 ms
15,104 KB |
testcase_17 | AC | 186 ms
27,648 KB |
testcase_18 | AC | 47 ms
11,648 KB |
testcase_19 | AC | 162 ms
25,600 KB |
testcase_20 | AC | 40 ms
8,192 KB |
testcase_21 | AC | 52 ms
13,440 KB |
testcase_22 | AC | 147 ms
23,808 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 15 ms
6,528 KB |
testcase_26 | AC | 79 ms
15,360 KB |
testcase_27 | AC | 85 ms
16,000 KB |
testcase_28 | AC | 153 ms
25,472 KB |
testcase_29 | AC | 12 ms
6,144 KB |
testcase_30 | AC | 157 ms
23,296 KB |
testcase_31 | AC | 108 ms
19,840 KB |
testcase_32 | AC | 68 ms
13,696 KB |
testcase_33 | AC | 171 ms
28,544 KB |
testcase_34 | AC | 50 ms
11,520 KB |
testcase_35 | AC | 160 ms
23,040 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 2 ms
5,376 KB |
testcase_38 | AC | 2 ms
5,376 KB |
testcase_39 | AC | 2 ms
5,376 KB |
testcase_40 | AC | 1 ms
5,376 KB |
testcase_41 | AC | 224 ms
26,240 KB |
testcase_42 | AC | 58 ms
11,940 KB |
testcase_43 | AC | 111 ms
14,976 KB |
testcase_44 | AC | 34 ms
6,016 KB |
testcase_45 | AC | 99 ms
13,056 KB |
testcase_46 | AC | 1 ms
5,376 KB |
testcase_47 | AC | 1 ms
5,376 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]) }