题目描述
给定一个 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

稠密图：邻接矩阵
稀疏图：邻接表

import java.io.*;
public class Main {
    static int N=510;
    static int n;
    static int[][] g=new int[N][N];
    static int[] dist=new int[N];
    static boolean[] st=new boolean[N]; 
    public static void main(String[] args) throws IOException{
       StreamTokenizer re=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
       re.nextToken();n=(int)re.nval;
       re.nextToken();int m=(int)re.nval;
       for(int i=0;i<N;i++){//初始化，所有边的距离为无穷大
            for(int j=0;j<N;j++){
                g[i][j]=0x3f3f3f;
                if(i == j){
                    g[i][j]=0;//环
                }
            }
        }
       while(m-->0){
       re.nextToken();int a=(int)re.nval;
       re.nextToken();int b=(int)re.nval; 
       re.nextToken();int c=(int)re.nval;
       g[a][b]=Math.min(g[a][b],c);//如果有重边，保留距离最短的边
       }
       System.out.print(dijkstra());
    }
    static int dijkstra(){
        for(int i=0;i<N;i++){//初始化每个点到起点（1号点）的距离为无穷大
            dist[i]=0x3f3f3f;
        }
        dist[1]=0;//更新1号点到1号点的距离为0
        //t更新其他点的距离
        for(int i=0;i<n;i++){
            int t=-1;
            for(int j=1;j<=n;j++){
                if(!st[j]&&(t==-1||dist[t]>dist[j])){
                    t=j;
                }
            }
             st[t] = true;//t加到集合里面去
             for(int j=1;j<=n;j++){
                 dist[j]=Math.min(dist[j],dist[t]+g[t][j]);
             }
        }
        if(dist[n]==0x3f3f3f)  return -1;
        return dist[n];
    }
}