题目描述
朴素Dijkstra
样例
import java.util.*;
public class Main{
static int N = 510,n,m, max = 0x3f3f3f3f;
static int[][] g = new int[N][N];//存每个点之间的距离
static int[] dist = new int[N];//存每个点到起点之间的距离
static boolean[] st = new boolean[N];//存已经确定了最短距离的点
public static int dijkstra(){
Arrays.fill(dist,max);//将dist数组一开始赋值成较大的数
dist[1] = 0; //首先第一个点是零
//从0开始,遍历n次,一次可以确定一个最小值
for(int i = 0 ; i < n ; i ++ ){
int t = -1; //t这个变量,准备来说就是转折用的
for(int j = 1 ; j <= n ; j ++ ){
/***
* 因为数字是大于1的,所以从1开始遍历寻找每个数
* 如果s集合中没有这个数
* 并且t == -1,表示刚开始 或者 后面的数比我新找的数距离起点的距离短
* 然后将j 的值赋值给 t
***/
if(!st[j] && (t == -1 || dist[j] < dist[t])){
t = j;
}
}
st[t] = true;//表示这个数是已经找到了确定了最短距离的点
//用已经确认的最短距离的点来更新后面的点
//就是用1到t的距离加上t到j的距离来更新从1到j的长度
for(int j = 1 ; j <= n ; j ++ ){
//
dist[j] = Math.min(dist[j],dist[t] + g[t][j]);
}
}
//如果最后n的长度没有改变,输出-1,没有找到;否则输出最短路n
if(dist[n] == max) return -1;
else return dist[n];
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
m = scan.nextInt();
//将他们每个点一开始赋值成一个较大的值
for(int i = 1 ; i <= n ; i ++ ){
Arrays.fill(g[i],max);
}
while(m -- > 0){
int a = scan.nextInt();
int b = scan.nextInt();
int c = scan.nextInt();
g[a][b] = Math.min(g[a][b],c);//这个因为可能存在重边,所以泽出最短的
}
int res = dijkstra();
System.out.println(res);
}
}