最短路径

[编程题]最短路径

热度指数：745 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定的有n个顶点和m条边的有向图中，求出s到t的最短距离。

输入描述:

输入第一行，四个整数n,m,s,t;
接下来m行，每行三个整数a,b,c，表示有条连接a到b的边，长度为c。
注意重边的情况。对于100%的数据，。边权。

输出描述:

输出s到t的最短距离，要是s无法到t，则输出-1。

示例1

输入

输出

算法知识视频讲解

查看答案及解析

Java

质子一号

不想自定义类, 想把代码尽量写的简单一点, 但一直卡在70%没有通过, 报错为数组越界, 想不明白为什么会数组越界. 或许是因为没有处理重边?

算法就是dijkstra, 首先不创建新数组, 就地执行, 不会出现问题, 然后使用一个dist来记录访问过的结点.

import java.util.*;
public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();

        int[][] matrix = new int[n + 1][n + 1];

        int from = input.nextInt();
        int to = input.nextInt();


        for (int i = 0; i < m; i++) {
            int r = input.nextInt();
            int c = input.nextInt();
            if (matrix[r][c] != 0) matrix[r][c] = Math.min(matrix[r][c], input.nextInt());
            else matrix[r][c] = input.nextInt();
        }

        input.close();

        if(n==0||m==0||from>n||to>n){
            System.out.println(-1);
            return;
        }

        dijkstra(matrix,from,to);

        System.out.println(matrix[from][to]==0?-1:matrix[from][to]);
    }

    public static void dijkstra(int[][] matrix, int source,int target) {
        int[] dist = new int[matrix.length];
        dist[source]++;
        int min = Integer.MAX_VALUE;
        int transI = 0;
        int minI = 0;
        for (int l = 1; l < matrix.length; l++) {
            for (int i = 1; i < matrix.length; i++) {
                if (dist[i] == 0) {
                    if (matrix[source][transI] != 0 && matrix[transI][i] != 0) {
                        if (matrix[source][i] != 0) {
                            matrix[source][i] = Math.min(matrix[source][i], matrix[source][transI] + matrix[transI][i]);
                        } else matrix[source][i] = matrix[source][transI] + matrix[transI][i];
                    }
                    if ( matrix[source][i]!=0&&min > matrix[source][i]) {
                        minI = i;
                        min = matrix[source][i];
                    }
                }
            }
            transI = minI;
            dist[transI]++;
            min = Integer.MAX_VALUE;
            if(transI==target) return;
        }
    }
}

编辑于 2020-04-14 10:00:58 回复(0)

Java

Mr.Benefit•Lucky

用的dijkstra单源最短路径算法，不知道为什么只能通过60%，也没有出错用例可以查看，看到评论区一个答案都没有，就把我自己的贴上来吧，望日后有大佬指点。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int n = in.nextInt();
            int m = in.nextInt();
            int start = in.nextInt();
            int end = in.nextInt();
            HashMap<Integer,Node> nodes = new HashMap<>();
            for (int i = 0; i < m; i++) {
                int from = in.nextInt();
                int to = in.nextInt();
                int weight = in.nextInt();
                if(!nodes.containsKey(from)){
                    nodes.put(from,new Node(from));
                }
                if(!nodes.containsKey(to)){
                    nodes.put(to,new Node(to));
                }
                Node fromNode = nodes.get(from);
                Node toNode = nodes.get(to);
                Edge newEdge = new Edge(weight,fromNode,toNode);
                fromNode.nexts.add(toNode);
                fromNode.edges.add(newEdge);
            }
            System.out.println(getShortestPath(nodes,start,end));
        }
        in.close();
    }

    public static int getShortestPath(HashMap<Integer,Node> nodes, int start, int end){
        HashMap<Node,Integer> distanceMap = new HashMap<>();
        distanceMap.put(nodes.get(start),0);
        HashSet<Node> selectedNodes = new HashSet<>();
        Node minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        while (minNode!=null){
            int distance = distanceMap.get(minNode);
            for(Edge edge : minNode.edges){
                Node toNode = edge.to;
                if(!distanceMap.containsKey(toNode)){
                    distanceMap.put(toNode,distance+edge.weight);
                }else {
                    distanceMap.put(toNode,Math.min(distanceMap.get(toNode),distance+edge.weight));
                }
            }
            selectedNodes.add(minNode);
            minNode = getMinDistanceAndUnselectedNode(distanceMap,selectedNodes);
        }
        return distanceMap.get(nodes.get(end));
    }

    private static Node getMinDistanceAndUnselectedNode(HashMap<Node, Integer> distanceMap, HashSet<Node> touchedNodes){
        Node minNode = null;
        int minDistance = Integer.MAX_VALUE;
        for(Map.Entry<Node,Integer> entry : distanceMap.entrySet()){
            Node node = entry.getKey();
            int distance = entry.getValue();
            if(!touchedNodes.contains(node) && distance<minDistance){
                minNode = node;
                minDistance = distance;
            }
        }
        return minNode;
    }

    static class Node{
        int id;
        ArrayList<Node> nexts;
        ArrayList<Edge> edges;

        public Node(int id) {
            this.id = id;
            this.nexts = new ArrayList<>();
            this.edges = new ArrayList<>();
        }
    }

    static class Edge{
        int weight;
        Node from;
        Node to;

        public Edge(int weight, Node from, Node to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }
    }
}

发表于 2020-04-05 15:07:08 回复(0)