BOJ11657: 타임머신

작성일

https://www.acmicpc.net/problem/11657

  • 요새는 Go가 재미남.. 재채점 당해서 눈물의 탈락을 한 벨만포드 다시 구현
  • 처음에 요상하게 구현한것 같은데, 다시 정리해보자
    • 안정성을 위해서 무조건 V * E 번 돈다
    • flag를 두어서 dist의 업데이트가 없다면 나간다.
    • V번동안 계속 업데이트 된다면, 음의 사이클이 있는것이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package main

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

const INF int = 1000000000

type Edge struct {
	u, v, cost int
}

func bellmanFord(n int, edges []Edge) (dist []int) {
	dist = make([]int, n)
	for i := range dist {
		dist[i] = INF
	}
	dist[1] = 0

	for i := 0; i < n; i++ {
		flag := false
		for _, e := range edges {
			if dist[e.u] >= INF {
				continue
			}
			if dist[e.v] > dist[e.u]+e.cost {
				dist[e.v] = dist[e.u] + e.cost
				flag = true
			}
		}
		if !flag {
			return dist
		}
	}
	return []int{}
}

func main() {
	r := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscan(r, &n, &m)
	edges := make([]Edge, m)

	for i := 0; i < m; i++ {
		e := &edges[i]
		fmt.Fscan(r, &e.u, &e.v, &e.cost)
	}
	dist := bellmanFord(n+1, edges)
	if len(dist) == 0 {
		fmt.Println(-1)
		return
	}
	for i := 2; i <= n; i++ {
		if dist[i] == INF {
			dist[i] = -1
		}
		fmt.Println(dist[i])
	}
}