题目描述
给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为正值。
请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x，y，z，表示存在一条从点x到点y的有向边，边长为z。
输出格式
输出一个整数，表示1号点到n号点的最短距离。
如果路径不存在，则输出-1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例：
3 3
1 2 2
2 3 1
1 3 4
输出样例：
3
算法go实现
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
const N = 510
var (
n, m int
g [N][N]int
dist [N]int
st [N]bool //存放当前已确定最短距离的点
)
func readline(r *bufio.Reader) []int {
s, _ := r.ReadString('\n')
ss := strings.Fields(s)
res := make([]int, len(ss))
for i, v := range ss {
res[i], _ = strconv.Atoi(v)
}
return res
}
func min(a, b int) int {
if a >= b {
return b
} else {
return a
}
}
func dijkstra() int {
// 初始化距离数组dist
for i := 0; i < N; i++ {
dist[i] = 0x3f3f3f3f
}
// 第一个点的距离是0
dist[1] = 0
// 迭代n次，每次先找到还没有确定最短路距离的点中距离当前点最短的点t
for i := 0; i < n; i++ {
t := -1 //不在s中的距离当前点最近的点，该点取值只是为了在st这个集合中找第一个点更新时方便所设，设成0和其他值都可以
for j := 1; j <= n; j++ {
if !st[j] && (t == -1 || dist[t] > dist[j]) {// dist[t] > dist[j]代表的意思是当前的t不是最短的
t = j
}
}
st[t] = true // 把t加到s集合中
// 用t更新其他点的距离
for j := 1; j <= n; j++ {
dist[j] = min(dist[j], dist[t]+g[t][j])
}
}
if dist[n] == 0x3f3f3f3f{
return -1
}
return dist[n]
}
func main() {
r := bufio.NewReader(os.Stdin)
in := readline(r)
n, m = in[0], in[1]
//初始化g
for i := 1; i <= n; i++ {
for j := 1; j <= n; j++ {
if i == j {
g[i][j] = 0
} else {
g[i][j] = 0x3f3f3f3f
}
}
}
for m > 0 {
m--
in := readline(r)
a, b, c := in[0], in[1], in[2]
g[a][b] = min(g[a][b], c)
}
fmt.Println(dijkstra())
}
