問題描述 給定一個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超時了。。。）
新聞熱點
疑難解答
