算法訓(xùn)練最短路

2019-11-14 09:50:44

字體：大中小

供稿：網(wǎng)友

問題描述給定一個(gè)n個(gè)頂點(diǎn)，m條邊的有向圖（其中某些邊權(quán)可能為負(fù)，但保證沒有負(fù)環(huán)）。請(qǐng)你計(jì)算從1號(hào)點(diǎn)到其他點(diǎn)的最短路（頂點(diǎn)從1到n編號(hào)）。

輸入格式第一行兩個(gè)整數(shù)n, m。

接下來的m行，每行有三個(gè)整數(shù)u, v, l，表示u到v有一條長(zhǎng)度為l的邊。

輸出格式共n-1行，第i行表示1號(hào)點(diǎn)到i+1號(hào)點(diǎn)的最短路。樣例輸入 3 3 1 2 -1 2 3 -1 3 1 2 樣例輸出 -1 -2 數(shù)據(jù)規(guī)模與約定對(duì)于10%的數(shù)據(jù)，n = 2，m = 2。

對(duì)于30%的數(shù)據(jù)，n <= 5，m <= 10。

對(duì)于100%的數(shù)據(jù)，1 <= n <= 20000，1 <= m <= 200000，-10000 <= l <= 10000，保證從任意頂點(diǎn)都能到達(dá)其他所有頂點(diǎn)。

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(); //頂點(diǎn)數(shù) int m = in.nextInt(); //邊數(shù) 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：數(shù)據(jù)量大，所以Java超時(shí)了。。。）