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:）求解本题的时间复杂度为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:)求解本题的时间复杂度为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
    
     [] 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
     
       list = new LinkedList
      
       ();        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
       
        [] listA = new ArrayList[n];        for(int i = 0;i < n;i++)            listA[i] = new ArrayList
        
         ();        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);    }}

上一篇：算法笔记_076:蓝桥杯练习结点选择（Java）

下一篇：算法笔记_074:子集和问题（Java）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！