結果
問題 | No.1065 電柱 / Pole (Easy) |
ユーザー | ccppjsrb |
提出日時 | 2020-05-29 22:36:35 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 3,419 bytes |
コンパイル時間 | 11,647 ms |
コンパイル使用メモリ | 230,772 KB |
実行使用メモリ | 37,504 KB |
最終ジャッジ日時 | 2024-04-23 23:50:13 |
合計ジャッジ時間 | 17,929 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 85 ms
16,512 KB |
testcase_03 | AC | 169 ms
33,920 KB |
testcase_04 | AC | 196 ms
33,920 KB |
testcase_05 | AC | 160 ms
37,504 KB |
testcase_06 | AC | 159 ms
37,376 KB |
testcase_07 | AC | 42 ms
11,136 KB |
testcase_08 | AC | 149 ms
29,824 KB |
testcase_09 | AC | 12 ms
5,376 KB |
testcase_10 | AC | 62 ms
16,384 KB |
testcase_11 | AC | 44 ms
11,008 KB |
testcase_12 | AC | 32 ms
10,496 KB |
testcase_13 | AC | 133 ms
26,368 KB |
testcase_14 | AC | 154 ms
28,928 KB |
testcase_15 | AC | 196 ms
33,920 KB |
testcase_16 | AC | 90 ms
19,328 KB |
testcase_17 | AC | 219 ms
34,432 KB |
testcase_18 | AC | 60 ms
14,336 KB |
testcase_19 | AC | 183 ms
31,744 KB |
testcase_20 | AC | 48 ms
10,624 KB |
testcase_21 | AC | 81 ms
18,432 KB |
testcase_22 | AC | 176 ms
30,976 KB |
testcase_23 | AC | 2 ms
5,376 KB |
testcase_24 | AC | 2 ms
5,376 KB |
testcase_25 | AC | 31 ms
9,472 KB |
testcase_26 | AC | 81 ms
17,920 KB |
testcase_27 | AC | 91 ms
20,608 KB |
testcase_28 | AC | 172 ms
29,696 KB |
testcase_29 | AC | 19 ms
6,272 KB |
testcase_30 | AC | 170 ms
32,256 KB |
testcase_31 | AC | 133 ms
24,448 KB |
testcase_32 | AC | 60 ms
15,488 KB |
testcase_33 | AC | 199 ms
31,104 KB |
testcase_34 | AC | 63 ms
15,360 KB |
testcase_35 | AC | 155 ms
30,720 KB |
testcase_36 | AC | 2 ms
5,376 KB |
testcase_37 | AC | 3 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 | 271 ms
30,720 KB |
testcase_42 | AC | 62 ms
12,032 KB |
testcase_43 | AC | 92 ms
17,536 KB |
testcase_44 | AC | 29 ms
7,552 KB |
testcase_45 | AC | 132 ms
18,432 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" "strconv" ) func getScanner(fp *os.File) *bufio.Scanner { scanner := bufio.NewScanner(fp) scanner.Split(bufio.ScanWords) scanner.Buffer(make([]byte, 1000005), 1000005) return scanner } func getNextString(scanner *bufio.Scanner) string { scanner.Scan() return scanner.Text() } func getNextInt(scanner *bufio.Scanner) int { i, _ := strconv.Atoi(getNextString(scanner)) return i } func getNextInt64(scanner *bufio.Scanner) int64 { i, _ := strconv.ParseInt(getNextString(scanner), 10, 64) return i } func getNextUint64(scanner *bufio.Scanner) uint64 { i, _ := strconv.ParseUint(getNextString(scanner), 10, 64) return i } func getNextFloat64(scanner *bufio.Scanner) float64 { i, _ := strconv.ParseFloat(getNextString(scanner), 64) return i } func main() { fp := os.Stdin wfp := os.Stdout cnt := 0 if os.Getenv("MASPY") == "ますピ" { fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT")) cnt = 1 } if os.Getenv("MASPYPY") == "ますピッピ" { wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10")) } scanner := getScanner(fp) writer := bufio.NewWriter(wfp) solve(scanner, writer) for i := 0; i < cnt; i++ { fmt.Fprintln(writer, "-----------------------------------") solve(scanner, writer) } writer.Flush() } func solve(scanner *bufio.Scanner, writer *bufio.Writer) { n := getNextInt(scanner) m := getNextInt(scanner) x := getNextInt(scanner) - 1 y := getNextInt(scanner) - 1 g := newGraph(n) pp := make([]int, n) qq := make([]int, n) for i := 0; i < n; i++ { pp[i] = getNextInt(scanner) qq[i] = getNextInt(scanner) } for i := 0; i < m; i++ { p := getNextInt(scanner) - 1 q := getNextInt(scanner) - 1 w := (pp[p]-pp[q])*(pp[p]-pp[q]) + (qq[p]-qq[q])*(qq[p]-qq[q]) g.appendEdge(p, q, i, math.Sqrt(float64(w))) g.appendEdge(q, p, i, math.Sqrt(float64(w))) } dd := &daikes{} heap.Init(dd) heap.Push(dd, newDaike(x, 0.0)) ww := make([]float64, n) for i := 0; i < n; i++ { ww[i] = 1e18 } visited := make([]int, n) for dd.Len() > 0 { d := heap.Pop(dd).(daike) if compare(ww[d.i], d.w) == -1 { continue } ww[d.i] = d.w if d.i == y { break } if visited[d.i] == 1 { continue } visited[d.i] = 1 for _, e := range g.e[d.i] { if compare(ww[e.to], e.w+d.w) == -1 { continue } ww[e.to] = e.w + d.w heap.Push(dd, newDaike(e.to, e.w+d.w)) } } fmt.Fprintf(writer, "%.9f\n", ww[y]) } func compare(a, b float64) int { eps := 1e-9 if a > b+eps { return 1 } if b > a+eps { return -1 } return 0 } func newDaike(i int, w float64) daike { return daike{ i: i, w: w, } } type daike struct { i int w float64 } type daikes []daike func (h daikes) Len() int { return len(h) } func (h daikes) Less(i, j int) bool { return h[i].w < h[j].w } func (h daikes) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *daikes) Push(x interface{}) { *h = append(*h, x.(daike)) } func (h *daikes) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x } type graph struct { v []*vertex e [][]*edge } func newGraph(n int) *graph { return &graph{ v: make([]*vertex, n), e: make([][]*edge, n), } } func (g *graph) appendEdge(from, to, id int, w float64) { g.e[from] = append(g.e[from], &edge{ to: to, id: id, w: w, }) } type vertex struct { } type edge struct { to, id int w float64 }