算法训练最短路

问题描述给定一个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，保证从任意顶点都能到达其他所有顶点。

代码语言：javascript复制

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

class Node {
    int now;
    int len;

    public Node(int now, int len) {
        super();
        this.now = now;
        this.len = len;
    }

}

class LinkedArr{
    ArrayList<Node> arr = new ArrayList<Node>();
}

public class Main {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();       //顶点数
        int m = in.nextInt();       //边数
        LinkedArr[] arr = new LinkedArr[n 1];
        int[] visit = new int[n 1];
        int[] dist = new int[n 1];
        for ( int i = 1 ; i <= n ; i  ){
            arr[i] = new LinkedArr();
            dist[i] = Integer.MAX_VALUE;
        }

        while(m--!=0){
            arr[in.nextInt()].arr.add(new Node(in.nextInt(), in.nextInt()));
        }

        for ( Node tmp : arr[1].arr){
            dist[tmp.now] = tmp.len;
        }
        visit[1] = 1;

        for ( int i = 1 ; i < n ; i  ){
            int min = Integer.MAX_VALUE;
            int minj = Integer.MAX_VALUE;
            for ( int j = 2  ; j <= n ; j  ){
                if ( visit[j] == 0 && dist[j] < min){
                    min = dist[j];
                    minj = j;
                }
            }
            visit[minj] = 1;
            for ( Node tmp : arr[minj].arr){
                if ( dist[minj]   tmp.len <= dist[tmp.now]){
                    dist[tmp.now] = dist[minj]   tmp.len;
                }
            }
        }

        for ( int i = 2 ; i <= n ; i  ){
            System.out.println(dist[i]);
        }

        in.close();
    }

}

（PS：数据量大，所以Java超时了。。。）

java ps

0 人点赞

算法训练 最短路

算法训练最短路