题解 | 邮递员送信

package main

import (
	"bufio"
	"container/heap"
	"fmt"
	"os"
)

type FastScanner struct {
	r   *bufio.Reader
	buf []byte
	i   int
	n   int
}

func NewFastScanner() *FastScanner {
	return &FastScanner{
		r:   bufio.NewReaderSize(os.Stdin, 1<<20),
		buf: make([]byte, 1<<20),
	}
}

func (fs *FastScanner) readByte() byte {
	if fs.i >= fs.n {
		fs.n, _ = fs.r.Read(fs.buf)
		fs.i = 0
		if fs.n == 0 {
			return 0
		}
	}
	b := fs.buf[fs.i]
	fs.i++
	return b
}

func (fs *FastScanner) NextInt() int {
	sign := 1
	b := fs.readByte()
	for b <= ' ' {
		if b == 0 {
			return 0
		}
		b = fs.readByte()
	}
	if b == '-' {
		sign = -1
		b = fs.readByte()
	}
	val := 0
	for b >= '0' && b <= '9' {
		val = val*10 + int(b-'0')
		b = fs.readByte()
	}
	return sign * val
}

type Edge struct {
	to int
	w  int64
}

type Item struct {
	node int
	dist int64
}

type PriorityQueue []Item

func (pq PriorityQueue) Len() int           { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int)      { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) {
	*pq = append(*pq, x.(Item))
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	x := old[len(old)-1]
	*pq = old[:len(old)-1]
	return x
}

const INF int64 = 1 << 60

func dijkstra(n int, g [][]Edge, src int) []int64 {
	dist := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		dist[i] = INF
	}
	dist[src] = 0

	pq := &PriorityQueue{}
	heap.Init(pq)
	heap.Push(pq, Item{node: src, dist: 0})

	for pq.Len() > 0 {
		cur := heap.Pop(pq).(Item)
		u := cur.node
		if cur.dist != dist[u] {
			continue
		}
		for _, e := range g[u] {
			nd := cur.dist + e.w
			if nd < dist[e.to] {
				dist[e.to] = nd
				heap.Push(pq, Item{node: e.to, dist: nd})
			}
		}
	}
	return dist
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	n := in.NextInt()
	m := in.NextInt()

	g := make([][]Edge, n+1)
	rg := make([][]Edge, n+1) // 反图

	for i := 0; i < m; i++ {
		u := in.NextInt()
		v := in.NextInt()
		w := int64(in.NextInt())
		g[u] = append(g[u], Edge{to: v, w: w})
		rg[v] = append(rg[v], Edge{to: u, w: w})
	}

	dist1 := dijkstra(n, g, 1)  // 1 -> i
	dist2 := dijkstra(n, rg, 1) // i -> 1（反图 1 -> i）

	var ans int64 = 0
	for i := 2; i <= n; i++ {
		if dist1[i] >= INF/2 || dist2[i] >= INF/2 {
			fmt.Fprintln(out, -1)
			return
		}
		ans += dist1[i] + dist2[i]
	}
	fmt.Fprintln(out, ans)
}