无向图最短路径

第一行为两个整数，结点数，边数
第二行到第m+1行各有3个数分别为：结点u，结点v，需要的时间段
最后一行为出发结点和到达结点

4 4
1 2 5
1 3 6
2 4 8
3 4 6
1 4 
示例输出12
4 4
1 2 25
1 3 18
2 4 28
3 4 22
1 4 7.9/8
示例输出40

BFS(参考迪杰斯特拉算法)

参考链接：https://blog.csdn.net/yu121380/article/details/79810233

public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            String[] arr1 = line.split(" ");
            int n = Integer.parseInt(arr1[0]);
            int m = Integer.parseInt(arr1[1]);
            //邻接矩阵
            int[][] arr = new int[n+1][n+1];
            //距离数组
            int[] dis = new int[n+1];
            //已拜访数组
            boolean[] vis = new boolean[n+1];
            for(int i = 0;i < n+1;i++){
                dis[i] = Integer.MAX_VALUE;
                vis[i] = false;
                for(int j = 0;j < n+1;j++){
                    arr[i][j] = Integer.MAX_VALUE;
                }
            }
            //构建邻接矩阵，除了连通的地方其他的都为int的最大值
            for(int i = 0;i < m;i++){
                String[] t = br.readLine().split(" ");
                int a = Integer.parseInt(t[0]);
                int b = Integer.parseInt(t[1]);
                int c = Integer.parseInt(t[2]);
                arr[a][b] = c;
                arr[b][a] = c;
            }
            //输入起点，终点
            String[] last = br.readLine().split(" ");
            int start = Integer.parseInt(last[0]);
            int end = Integer.parseInt(last[1]);

            dis[start] = 0;
            for(int i = 1;i <= n;i++){
                int minx = Integer.MAX_VALUE;
                int minmark = 1;;
                for(int j = 1;j <= n;j++){
                    if(vis[j] == false && dis[j] <= minx){
                        minx = dis[j];
                        minmark = j;
                    }
                }
                vis[minmark] = true;
                for(int j =1;j<=n;j++){
                    if(vis[j]==false && arr[minmark][j] != Integer.MAX_VALUE &&dis[j]>dis[minmark]+arr[minmark][j])
                        dis[j]=dis[minmark]+arr[minmark][j];
                }
            }
            System.out.println(dis[n]);            
        }
    }

DFS

static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            String[] arr1 = line.split(" ");
            int n = Integer.parseInt(arr1[0]);
            int m = Integer.parseInt(arr1[1]);
            int[][] arr = new int[n+1][n+1];
            boolean[] flag = new boolean[n+1];
            for(int i = 0;i < n+1;i++){
                for(int j = 0;j < n+1;j++){
                    arr[i][j] = Integer.MAX_VALUE;
                }
            }
            for(int i = 0;i < m;i++){
                String[] t = br.readLine().split(" ");
                int a = Integer.parseInt(t[0]);
                int b = Integer.parseInt(t[1]);
                int c = Integer.parseInt(t[2]);
                arr[a][b] = c;
                arr[b][a] = c;
            }

            String[] last = br.readLine().split(" ");
            int start = Integer.parseInt(last[0]);
            int end = Integer.parseInt(last[1]);
            flag[start] = true;
            fincycle(arr, start, end, 0,flag,n);
            System.out.println(min);
        }
    }
    static void fincycle(int[][] arr,int s,int e,int cnt,boolean[] flag,int n){
        if(cnt > min){
            return;
        }
        if(s == e){
            if(cnt < min){
                min = cnt;
            }
            return;
        }
        for(int i = 1;i <= n;i++){
            if(arr[s][i] != Integer.MAX_VALUE && flag[i] == false){
                flag[i] = true;
                fincycle(arr, i, e, cnt+arr[s][i],flag,n);
                flag[i] = false;
            }
        }
    }