代码片段仓库

func knapsack(weights, values []int, capacity int) int {
	n := len(weights)
	dp := make([][]int, n+1)
	for i := 1; i <= n; i++ {
		for w := 0; w <= capacity; w++ {
			dp[i][w] = dp[i-1][w]
			if w >= weights[i-1] {
				drop := values[i-1] + dp[i-1][w-weights[i-1]]
				if dp[i][w] < drop {
					dp[i][w] = drop
				}
			}
		}
	}
	return dp[n][capacity]
}

func quickPow(base, exp int) int {
	result := 1
	for exp > 0 {
		if exp&1 == 1 {
			result = result * base
		}
		base = base * base
		exp >>= 1
	}
	return result
}

func quickPow(base, exp int) int {
	result := 1
	for exp > 0 {
		if exp&1 == 1 {
			result = result * base
		}
		base = base * base
		exp >>= 1
	}
	return result
}

func dijkstra(graph map[int][]int, start int) []int {
	n := len(graph)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[start] = 0

	visited := make([]bool, n)

	for i := 0; i < n; i++ {
		u := -1
		for j := 0; j < n; j++ {
			if !visited[j] && (u == -1 || dist[j] < dist[u]) {
				u = j
			}
		}
		visited[u] = true

		for v, weight := range graph[u] {
			if weight == 0 {
				continue
			}
			if newDist := dist[u] + weight; newDist < dist[v] {
				dist[v] = newDist
			}
		}
	}
	return dist
}

func dijkstra(graph map[int][]int, start int) []int {
	n := len(graph)
	dist := make([]int, n)
	for i := range dist {
		dist[i] = math.MaxInt32
	}
	dist[start] = 0

	visited := make([]bool, n)

	for i := 0; i < n; i++ {
		u := -1
		for j := 0; j < n; j++ {
			if !visited[j] && (u == -1 || dist[j] < dist[u]) {
				u = j
			}
		}
		visited[u] = true

		for v, weight := range graph[u] {
			if weight == 0 {
				continue
			}
			if newDist := dist[u] + weight; newDist < dist[v] {
				dist[v] = newDist
			}
		}
	}
	return dist
}

func floydWarshall(graph [][]int) [][]int {
	n := len(graph)
	// Initialize dist matrix
	dist := make([][]int, n)
	for i := 0; i < n; i++ {
		dist[i] = make([]int, n)
		copy(dist[i], graph[i])
	}

	for k := 0; k < n; k++ {
		for i := 0; i < n; i++ {
			for j := 0; j < n; j++ {
				if dist[i][k] != math.MaxInt32 && dist[k][j] != math.MaxInt32 {
					if newDist := dist[i][k] + dist[k][j]; newDist < dist[i][j] {
						dist[i][j] = newDist
					}
				}
			}
		}
	}
	return dist
}