OJ-简单的最短路径

 示例1

输入
7 7 1 7
1 2 1
2 3 3
2 4 5
2 5 6
4 6 3
6 7 1
6 5 7
输出
10

分析：

	0	1	2	3	4	5	6
0		1
1			3	5	6
2
3						3
4
5					7		1
6

 

 示例2：顶点5到顶点6可达

输入
7 7 1 7
1 2 1
2 3 3
2 4 5
2 5 6
4 6 3
6 7 1
5 6 1
输出
9

代码实现

import java.util.PriorityQueue;
import java.util.Scanner;

public class 简单的最短路径 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt() - 1;
        int t = in.nextInt() - 1;

        int[][] map = new int[n][n];
        for (int i = 0; i < m; i++) {
            int x = in.nextInt() - 1;
            int y = in.nextInt() - 1;
            int z = in.nextInt();
            map[x][y] = z;
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        dfs(map, s, t, queue, 0);
        if (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }

    }

    private static void dfs(int[][] map, int s, int t, PriorityQueue<Integer> queue, int path) {
            int temp = path;
            for (int i = 0; i < map[0].length; i++) {
            if (map[s][i] != 0) {
                path += map[s][i];
                if (i == t) {
                    queue.add(path);
                }
                dfs(map, i, t, queue, path);
                path = temp;
            }
        }
    }
}

144.【华为OD机试高分必刷题目】简单的最短路径（Java-Dijkstra算法实现）-CSDN博客

原文地址：https://blog.csdn.net/wsd_ontheroad/article/details/143082773

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！