SPOJ 3700 "Easy Dijkstra Problem" EZDIJKST

問題：http://www.spoj.pl/problems/EZDIJKST/

Go言語で書き直してみた．

package main

import (
	"scanner"
	"os"
	"strconv"
	"bufio"
	"container/vector"
	"container/heap"
)

func run() {
	for t := next(); t > 0; t-- {
		g := NewGraph(next())
		for k := next(); k > 0; k-- {
			g.cost[next()-1][next()-1] = next()
		}
		c := g.Dijkstra(next()-1, next()-1)
		if c == 0 {
			println("NO")
		} else {
			printIntln(c)
		}
	}

}

func main() {
	run()
	ioend()
}

var (
	in  scanner.Scanner
	out *bufio.Writer = bufio.NewWriter(os.Stdout)
)

func init() {
	in.Init(os.Stdin)
}

func ioend() {
	out.Flush()
}

func next() (n int) {
	in.Scan()
	sig := 1
	if in.TokenText() == "-" {
		sig = -1
		in.Scan()
	}
	n, _ = strconv.Atoi(in.TokenText())
	return n * sig
}

func printIntln(n int) {
	println(strconv.Itoa(n))
}

func println(str string) {
	out.WriteString(str)
	out.WriteString("\n")
}

type Graph struct {
	n    int
	cost [][]int
}

func NewGraph(n int) *Graph {
	cost := make([][]int, n)
	for i := 0; i < n; i++ {
		cost[i] = make([]int, n)
	}
	return &Graph{n, cost}
}

type Edge struct {
	from, to, cost int
}

func (e *Edge) Less(o interface{}) bool {
	return e.cost < o.(*Edge).cost
}

func (g *Graph) Dijkstra(s, e int) (c int) {
	used := make([]bool, g.n)
	for i := 0; i < g.n; i++ {
		used[i] = i == s
	}
	q := new(vector.Vector)
	heap.Init(q)
	for i := 0; i < g.n; i++ {
		if g.cost[s][i] > 0 {
			heap.Push(q, &Edge{s, i, g.cost[s][i]})
		}
	}
	for q.Len() > 0 {
		edge := heap.Pop(q).(*Edge)
		if edge.to == e {
			c = edge.cost
			break
		}
		used[edge.to] = true
		for i := 0; i < g.n; i++ {
			if !used[i] && g.cost[edge.to][i] > 0 {
				heap.Push(q, &Edge{edge.to, i, edge.cost + g.cost[edge.to][i]})
			}
		}
	}
	return
}