1 问题描述

问题描述

给定一个n个顶点，m条边的有向图（其中某些边权可能为负，但保证没有负环）。请你计算从1号点到其他点的最短路（顶点从1到n编号）。

输入格式

第一行两个整数n, m。

接下来的m行，每行有三个整数u, v, l，表示u到v有一条长度为l的边。

输出格式

共n-1行，第i行表示1号点到i+1号点的最短路。

样例输入

3 3
1 2 -1
2 3 -1
3 1 2

样例输出

-1
-2

数据规模与约定

对于10%的数据，n = 2，m = 2。

对于30%的数据，n <= 5，m <= 10。

对于100%的数据，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保证从任意顶点都能到达其他所有顶点。

2 解决方案

2.1 floyd算法解决

使用floyd算法（ps:算法笔记_069:Floyd算法简单介绍（Java））求解本题的时间复杂度为O(n^3)，下面代码在系统中测评分为40，原因：运行超时。以下代码仅供参考。

具体代码如下：

import java.util.Scanner;

public class Main {
    
    public void floyd(long[][] adjMatrix) {
        for(int k = 0;k < adjMatrix.length;k++) {
            for(int i = 0;i < adjMatrix.length;i++) {
                for(int j  = 0;j < adjMatrix.length;j++) {
                    if(adjMatrix[i][k] != Integer.MAX_VALUE && adjMatrix[k][j] != Integer.MAX_VALUE) {
                        if(adjMatrix[i][j] > adjMatrix[i][k] + adjMatrix[k][j])
                            adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                    }
                }
            }
         }
        for(int i = 1;i < adjMatrix.length;i++)
            System.out.println(adjMatrix[0][i]);
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        if(n > 20000 || n < 1 || m > 200000 || m < 1)
            return;
        long[][] adjMatrix = new long[n][n];
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < n;j++)
                adjMatrix[i][j] = Integer.MAX_VALUE;
        }
        for(int i = 0;i < m;i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int value = in.nextInt();
            if(value > 10000 || value < -10000)
                return;
            adjMatrix[a - 1][b - 1] = value;
        }
        test.floyd(adjMatrix);
    }
    
}

2.2 spfa算法解决

使用spfa算法(PS:算法笔记_071:SPFA算法简单介绍（Java）)求解本题的时间复杂度为O(m*E)(PS:其中E为给定边的数目，m为图中顶点进出链表的总次数，一般不大于2*n，n为图中总顶点数)。下面的给出的代码，在系统中测评分为70或者80分（PS：同样代码提交了两次，评分不一样），具体原因：运行超时。可能是Java语言编译时间没有C/C++那么快，所以不能在1s内完成。如果是楼主自己代码问题，还请路过同学不吝赐教啊~

具体代码如下：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    
    static class edge {
        public int a;  //边的起点
        public int b;  //边的终点
        public int value;  //边的权值
        
        edge(int a, int b, int value) {
            this.a = a;
            this.b = b;
            this.value = value;
        }
    }
    
    public void spfa(ArrayList<edge>[] listA, int n) {
        long[] result = new long[n];
        int[] num = new int[n];
        boolean[] used = new boolean[n];
        for(int i = 1;i < n;i++) {
            result[i] = Integer.MAX_VALUE;
            used[i] = false;
        }
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(0);
        num[0] = 1;
        used[0] = true;
        while(list.size() > 0) {
            int start = list.getFirst();
            for(int i = 0, length = listA[start].size();i < length;i++) {
                int b = listA[start].get(i).b;
                int value = listA[start].get(i).value;
                if(result[b - 1] > result[start] + value) {
                    result[b - 1] = result[start] + value;
                    if(!used[b - 1]) {
                        used[b - 1] = true;
                        list.add(b - 1);
                        num[b - 1]++;
                        if(num[b - 1] > n)
                            return;
                    }
                }
            }
            list.removeFirst();
            used[start] = false;    
        }
        for(int i = 1;i < n;i++)
            System.out.println(result[i]);
        return;
    }
    
    public static void main(String[] args) {
        Main test = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        if(n > 20000 || n < 1 || m > 200000 || m < 1)
            return;
        @SuppressWarnings("unchecked")
        ArrayList<edge>[] listA = new ArrayList[n];
        for(int i = 0;i < n;i++)
            listA[i] = new ArrayList<edge>();
        for(int i = 0;i < m;i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            int value = in.nextInt();
            if(value > 10000 || value < -10000)
                return;
            listA[a - 1].add(new edge(a, b, value));
        }
        test.spfa(listA, n);
    }
}

算法笔记_075:蓝桥杯练习 最短路（Java）

1 问题描述

2 解决方案

2.1 floyd算法解决

2.2 spfa算法解决

算法笔记_075:蓝桥杯练习最短路（Java）