给定一个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，保证从任意顶点都能到达其他所有顶点。
import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int[][] map; static boolean[] vis; static int[] dis; static int MAX = 1000000; public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); map = new int[n + 1][n + 1]; vis = new boolean[n + 1]; dis = new int[n + 1]; init(map); while (m-- > 0) { int u = sc.nextInt(); int v = sc.nextInt(); int l = sc.nextInt(); map[u][v] = l; } spfa(1, n); for (int i = 2; i <= n; i++) System.out.println(dis[i]); } private static void spfa(int start, int n) { // TODO Auto-generated method stub int x; Queue<Integer> q = new LinkedList<Integer>(); Arrays.fill(dis, MAX); dis[start] = 0; q.offer(start); vis[start] = true; while (!q.isEmpty()) { x = q.poll(); vis[x] = false; for (int i = 1; i <= n; i++) if (dis[i] > dis[x] + map[x][i]) { dis[i] = dis[x] + map[x][i]; if (!vis[i]) { q.offer(i); vis[i] = true; } } } } private static void init(int[][] map) { // TODO Auto-generated method stub for (int i = 1; i < map.length; i++) { Arrays.fill(map[i], MAX); } } }
