算法訓練最短路

2019-11-14 09:56:36

字體：大中小

來源：轉載

供稿：網友

問題描述給定一個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超時了。。。）