71 lines
1.4 KiB
Go
71 lines
1.4 KiB
Go
|
package main
|
||
|
|
|
||
|
|
type Next struct {
|
||
|
|
Visited map[int]bool
|
||
|
|
Time int
|
||
|
|
Node int
|
||
|
|
}
|
||
|
|
|
||
|
|
type Edge struct {
|
||
|
|
To int
|
||
|
|
Time int
|
||
|
|
}
|
||
|
|
|
||
|
|
// Horrible, unoptimised solution that I could come up with
|
||
|
|
// Should learn how to do depth-first-search properly
|
||
|
|
func maximalPathQuality(values []int, edges [][]int, maxTime int) int {
|
||
|
|
next := []*Next{
|
||
|
|
{
|
||
|
|
Visited: map[int]bool{0: true},
|
||
|
|
Time: 0,
|
||
|
|
Node: 0,
|
||
|
|
},
|
||
|
|
}
|
||
|
|
es := map[int][]*Edge{}
|
||
|
|
for _, edge := range edges {
|
||
|
|
_, ok := es[edge[0]]
|
||
|
|
if !ok {
|
||
|
|
es[edge[0]] = []*Edge{}
|
||
|
|
}
|
||
|
|
_, ok = es[edge[1]]
|
||
|
|
if !ok {
|
||
|
|
es[edge[1]] = []*Edge{}
|
||
|
|
}
|
||
|
|
es[edge[0]] = append(es[edge[0]], &Edge{To: edge[1], Time: edge[2]})
|
||
|
|
es[edge[1]] = append(es[edge[1]], &Edge{To: edge[0], Time: edge[2]})
|
||
|
|
}
|
||
|
|
maxQuality := values[0]
|
||
|
|
for len(next) != 0 {
|
||
|
|
_next := []*Next{}
|
||
|
|
for _, n := range next {
|
||
|
|
if n.Node == 0 && n.Time != 0 {
|
||
|
|
q := 0
|
||
|
|
for node := range n.Visited {
|
||
|
|
q += values[node]
|
||
|
|
}
|
||
|
|
if q > maxQuality {
|
||
|
|
maxQuality = q
|
||
|
|
}
|
||
|
|
}
|
||
|
|
nedges, ok := es[n.Node]
|
||
|
|
if ok {
|
||
|
|
for _, nedge := range nedges {
|
||
|
|
if !(n.Time+nedge.Time > maxTime) {
|
||
|
|
v := map[int]bool{nedge.To: true}
|
||
|
|
for key := range n.Visited {
|
||
|
|
v[key] = true
|
||
|
|
}
|
||
|
|
_next = append(_next, &Next{
|
||
|
|
Visited: v,
|
||
|
|
Time: n.Time + nedge.Time,
|
||
|
|
Node: nedge.To,
|
||
|
|
})
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
next = _next
|
||
|
|
}
|
||
|
|
return maxQuality
|
||
|
|
}
|