第二题：迪杰斯特拉算法，在创建图的时候卡了挺久的。。

import java.util.*;

class Edge implements Comparable<Edge> {
    public int weight;
    public Node from;
    public Node to;

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

    @Override
    public int compareTo(Edge o) {
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "weight=" + weight +
                ", from=" + from +
                ", to=" + to +
                '}';
    }
}

class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

class Node {
    public int value;
    public int in;
    public int out;
    public ArrayList<Node> nexts;
    public ArrayList<Edge> edges;

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

public class Main1 {
    //记录距离树最近边edges对应的权值
    static private HashMap<Node, Integer> powers;
    //记录横切边
    static private PriorityQueue<Edge> pq;
    //记录顶点
    static private Node origin;
    static private Graph graph;

    public static void init(Integer[][] matrix, int p, int n) {
        graph = createGraph(matrix);
        origin = graph.nodes.get(p);
        powers = new HashMap<>(n);
        pq = new PriorityQueue<>(n);
        for (int i = 0; i < n; i++) {
            powers.put(graph.nodes.get(i), Integer.MAX_VALUE);
        }
        find();
    }

    private static void find() {
        //从起点开始
        powers.put(origin, 0);
        pq.offer(new Edge(-1, origin, origin));
        relax(origin);

        //不断放松权值最小的边
        while (!pq.isEmpty()) {
            Edge min = pq.poll();
            relax(min.to);
        }
    }

    //对顶点的所有邻接边检查，松弛权值比较大的顶点，修正无效边
    private static void relax(Node from) {
        for (Edge edge : from.edges) {
            Node to = edge.to;
            int newPower = powers.get(from) + edge.weight;
            //经过顶点from的边的路径权值比原来更小，把to的边的起点修改为from，把到to的权值修改为更小的
            if (powers.get(to) > newPower) {
                powers.put(to, newPower);
                if (pq.contains(edge))
                    pq.remove(edge);
                edge.weight = newPower;
                pq.offer(edge);
            }
        }
    }

    //获取到某一顶点的权值
    public static int getPower(int vertex) {
        Node node = graph.nodes.get(vertex);
        return powers.get(node);
    }

    public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == -1)
                    continue;
                Integer from = i;
                Integer to = j;
                if (!graph.nodes.containsKey(from)) {
                    graph.nodes.put(from, new Node(from));
                }
                if (!graph.nodes.containsKey(to)) {
                    graph.nodes.put(to, new Node(to));
                }
                Node fromNode = graph.nodes.get(from);
                Node toNode = graph.nodes.get(to);
                Edge newEdge = new Edge(matrix[i][j], fromNode, toNode);
                fromNode.nexts.add(toNode);
                fromNode.out++;
                toNode.in++;
                fromNode.edges.add(newEdge);
                graph.edges.add(newEdge);
            }
        }
        return graph;
    }

    public static void main(String[] args) {
//        Integer[][] matrix = {
//                {-1, 1, 4, -1, -1, -1},
//                {1, -1, 2, 7, 5, -1},
//                {4, 2, -1, -1, 1, -1},
//                {-1, 7, -1, -1, 3, 2},
//                {-1, 5, 1, 3, -1, 6},
//                {-1, -1, -1, 2, 6, -1}
//        };
//        init(matrix,0,6);
//        for (int i = 0; i < 6; i++) {
//            if (i == 0)
//                continue;
//            System.out.print(getPower(i));
//            if(i != 6 - 1)
//                System.out.print(",");
//        }
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            int p = scanner.nextInt();
            Integer[][] matrix = new Integer[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = scanner.nextInt();
                }
            }
            init(matrix, p, n);
            for (int i = 0; i < n; i++) {
                if (i == p)
                    continue;
                System.out.print(getPower(i)+",");
            }
            System.out.println();
        }
    }
}