글 읽기 - 1238번 파티 플로이드-와샬 로 풀 수 있는 문제인가요?

bupjae 6년 전 0

n = 1000 이길래 O(n^3) 인 플로이드-와샬 로 시간내에 풀 수 있을지 반신반의 했지만, "알고리즘 분류"에 플로이드-와샬 이 있길래 이걸로도 되나보다 하고 답안을 작성했습니다.

아니나 다를까... 저를 맞이하는 채점 결과는 TLE

코딩 실수로 TLE를 받았을 가능성도 있으니까 제가 작성한 답안을 올립니다.

이 문제가 정말로 플로이드-와샬 을 의도한 것인지, 주어진 제한 시간 내에 풀 수 있는 문제인지 확인 부탁드립니다.

package main

import (
	"bufio"
	"fmt"
	"os"
)

var in = bufio.NewScanner(os.Stdin)

func NextInt() int {
	in.Scan()
	r := 0
	for _, c := range in.Bytes() {
		r *= 10
		r += int(c - '0')
	}
	return r
}

func main() {
	in.Split(bufio.ScanWords)
	n, m, x := NextInt(), NextInt(), NextInt()
	g := make(map[int]map[int]int)
	for i := 1; i <= n; i++ {
		g[i] = make(map[int]int)
		g[i][i] = 0
	}
	for ; m > 0; m-- {
		a, b, c := NextInt(), NextInt(), NextInt()
		g[a][b] = c
	}
	for k := 1; k <= n; k++ {
		for i := 1; i <= n; i++ {
			a, ok := g[i][k]
			if !ok {
				continue
			}
			for j := 1; j <= n; j++ {
				b, ok := g[k][j]
				if !ok {
					continue
				}
				if c, ok := g[i][j]; !ok || c > a+b {
					g[i][j] = a + b
				}
			}
		}
	}
	r := 0
	for i := 1; i <= n; i++ {
		if s := g[i][x] + g[x][i]; r < s {
			r = s
		}
	}
	fmt.Println(r)
}