結果
問題 | No.17 2つの地点に泊まりたい |
ユーザー | yuki2006 |
提出日時 | 2016-10-20 01:09:07 |
言語 | Go (1.22.1) |
結果 |
AC
|
実行時間 | 2 ms / 5,000 ms |
コード長 | 3,057 bytes |
コンパイル時間 | 10,831 ms |
コンパイル使用メモリ | 230,748 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-15 01:37:17 |
合計ジャッジ時間 | 11,620 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 1 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 1 ms
5,248 KB |
testcase_05 | AC | 1 ms
5,248 KB |
testcase_06 | AC | 1 ms
5,248 KB |
testcase_07 | AC | 1 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 1 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 1 ms
5,248 KB |
testcase_13 | AC | 1 ms
5,248 KB |
testcase_14 | AC | 1 ms
5,248 KB |
testcase_15 | AC | 1 ms
5,248 KB |
testcase_16 | AC | 1 ms
5,248 KB |
testcase_17 | AC | 1 ms
5,248 KB |
testcase_18 | AC | 1 ms
5,248 KB |
testcase_19 | AC | 1 ms
5,248 KB |
testcase_20 | AC | 1 ms
5,248 KB |
testcase_21 | AC | 1 ms
5,248 KB |
testcase_22 | AC | 1 ms
5,248 KB |
testcase_23 | AC | 1 ms
5,248 KB |
testcase_24 | AC | 1 ms
5,248 KB |
testcase_25 | AC | 1 ms
5,248 KB |
testcase_26 | AC | 1 ms
5,248 KB |
ソースコード
package mainimport ("bufio""os""strconv""fmt")func main() {sc := NewScanner()N := sc.NextInt()stay := make([]int, N)for i := 0; i < N; i++ {stay[i] = sc.NextInt()}edge := make([][]int, N)for i := 0; i < N; i++ {edge[i] = make([]int, N)fill(edge[i], -1)}M := sc.NextInt()for i := 0; i < M; i++ {A, B, C := sc.NextInt(), sc.NextInt(), sc.NextInt()edge[A][B] = Cedge[B][A] = C}for k := 0; k < N; k++ {for i := 0; i < N; i++ {if edge[i][k] == -1 {continue}for j := 0; j < N; j++ {if edge[k][j] == -1 {continue}if edge[i][j] == -1 || edge[i][j] > edge[i][k] + edge[k][j] {edge[i][j] = edge[i][k] + edge[k][j]}}}}mn := -1for i := 1; i < N - 1; i++ {if edge[0][i] == -1 {continue}for j := 1; j < N - 1; j++ {if i == j {continue}if edge[i][j] == -1 || edge[i][N - 1] == -1 {continue}s := edge[0][i] + edge[i][j] + edge[j][N - 1] + stay[i] + stay[j]if mn == -1 || mn > s {mn = s}}}fmt.Println(mn)}type Scanner struct {r *bufio.Readerbuf []bytep int}func NewScanner() *Scanner {rdr := bufio.NewReaderSize(os.Stdin, 1000)return &Scanner{r:rdr}}func (s *Scanner) Next() string {s.pre()start := s.pfor ; s.p < len(s.buf); s.p++ {if s.buf[s.p] == ' ' {break}}result := string(s.buf[start:s.p])s.p++return result}func (s *Scanner) NextLine() string {s.pre()start := s.ps.p = len(s.buf)return string(s.buf[start:])}func (s *Scanner) NextInt() int {v, _ := strconv.Atoi(s.Next())return v}func (s *Scanner) NextInt64() int64 {v, _ := strconv.ParseInt(s.Next(), 10, 64)return v}func (s *Scanner) NextIntArray() []int {s.pre()start := s.presult := []int{}for ; s.p < len(s.buf) + 1; s.p++ {if s.p == len(s.buf) || s.buf[s.p] == ' ' {v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 0)result = append(result, int(v))start = s.p + 1}}return result}func (s *Scanner) NextInt64Array() []int64 {s.pre()start := s.presult := []int64{}for ; s.p < len(s.buf) + 1; s.p++ {if s.p == len(s.buf) || s.buf[s.p] == ' ' {v, _ := strconv.ParseInt(string(s.buf[start:s.p]), 10, 64)result = append(result, v)start = s.p + 1}}return result}func (s *Scanner) NextMap() map[int]bool {s.pre()start := s.pmp := map[int]bool{}for ; s.p < len(s.buf); s.p++ {if s.buf[s.p] == ' ' {v, _ := strconv.Atoi(string(s.buf[start:s.p]))mp[v] = truestart = s.p + 1}}v, _ := strconv.Atoi(string(s.buf[start:s.p]))mp[v] = truereturn mp}func (s *Scanner) pre() {if s.p >= len(s.buf) {s.readLine()s.p = 0}}func (s *Scanner) readLine() {s.buf = make([]byte, 0)for {l, p, e := s.r.ReadLine()if e != nil {panic(e)}s.buf = append(s.buf, l...)if !p {break}}}func fill(arr []int, v int) {for i := 0; i < len(arr); i++ {arr[i] = v}}func min(a int, b int) int {if a < b {return a}return b}