算法训练最短路

2019-11-14 10:01:50

字体：大中小

来源：转载

供稿：网友

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

package 最短路;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超时了。。。）