题目描述
给定一个 $n$ 个点 $m$ 条边的有向图,图中可能存在重边和自环,所有边权均为非负值。
请你求出 $1$ 号点到 $n$ 号点的最短距离,如果无法从 $1$ 号点走到 $n$ 号点,则输出 $−1$。
输入格式
第一行包含整数 $n$ 和 $m$。
接下来 $m$ 行每行包含三个整数 $x,y,z$,表示存在一条从点 $x$ 到点 $y$ 的有向边,边长为 $z$。
输出格式
输出一个整数,表示 $1$ 号点到 $n$ 号点的最短距离。
如果路径不存在,则输出 $−1$。
数据范围
$1≤n,m≤1.5×10^5$,
图中涉及边长均不小于 0,且不超过 10000。
样例
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
Go 代码
package main
import (
"fmt"
"strconv"
"strings"
"os"
"bufio"
"container/heap"
)
const N = 150010
const INF = 1000000010
var n, m int
var d = [N]int{}
var he = [N]int{}
var e = [N]int{}
var w = [N]int{}
var ne = [N]int{}
var st = [N]bool{}
var idx = 1
type myHeap [][2]int
func (m myHeap) Len() int {
return len(m)
}
func (m myHeap) Less(i, j int) bool {
return m[i][1] < m[j][1]
}
func (m myHeap) Swap(i, j int) {
m[i], m[j] = m[j], m[i]
}
func (m *myHeap) Push(x interface{}) {
*m = append(*m, x.([2]int))
}
func (m *myHeap) Pop() interface{} {
old := *m
n := len(old)
x := old[n - 1]
*m = old[0 : n - 1]
return x
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func add(a, b, c int) {
e[idx] = b
w[idx] = c
ne[idx] = he[a]
he[a] = idx
idx ++
}
func dijkstra() int {
for i := 1; i <= n; i ++ {
d[i] = INF
}
d[1] = 0
h := &myHeap{}
heap.Init(h)
heap.Push(h, [2]int{1, 0})
for h.Len() > 0 {
temp := heap.Pop(h)
t := temp.([2]int)
dis := t[1]
if st[t[0]] {
continue
}
st[t[0]] = true
for i := he[t[0]]; i != -1; i = ne[i] {
j := e[i]
if d[j] > dis + w[i] {
d[j] = dis + w[i]
heap.Push(h, [2]int{j, d[j]})
}
}
}
if d[n] == INF {
return -1
}
return d[n]
}
func main(){
fmt.Scanln(&n, &m)
for i := 1; i <= n; i ++ {
he[i] = -1
}
scanner := bufio.NewScanner(os.Stdin)
bs := make([]byte, 1024*4000)
scanner.Buffer(bs, len(bs))
for m > 0 {
m --
scanner.Scan()
line := strings.Split(scanner.Text(), " ")
a, _ := strconv.Atoi(line[0])
b, _ := strconv.Atoi(line[1])
c, _ := strconv.Atoi(line[2])
add(a, b, c)
}
res := dijkstra()
fmt.Println(res)
}