蓝桥杯 算法训练 最短路

算法训练 最短路  
时间限制：1.0s   内存限制：256.0MB
   
问题描述

给定一个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

使用Dijkstra算法。

import java.util.ArrayList;
import java.util.Scanner;

class Node
{
int now, len;
public Node(int now, int len)
{
this.now = now;
this.len = len;
}
}

class LinkedArr
{
ArrayList<Node> arr = new ArrayList<Node>();
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        LinkedArr arr[] = new LinkedArr[n+1];
        for(int i = 1; i <= n; ++i)
        {
        arr[i] = new LinkedArr();
        }

        int flag[] = new int[n+1];
        int dist[] = new int[n+1];
        int m = sc.nextInt();

        while(m-- != 0)
        {
        arr[sc.nextInt()].arr.add(new Node(sc.nextInt(), sc.nextInt()));
        }

        for(int i = 1; i <= n; ++i)
        {
        flag[i] = 0;
        dist[i] = Integer.MAX_VALUE;
        }
        for(Node temp : arr[1].arr)
        {
        dist[temp.now] = temp.len;
        }
        flag[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(flag[j] == 0 && dist[j] < min)
            {
            min = dist[j];
            minj = j; 
            }
            }
            //System.out.println(min);
            flag[minj] = 1;
            for(Node temp : arr[minj].arr)
            {
            if(dist[minj] + temp.len <= dist[temp.now])
            {
            dist[temp.now] = dist[minj] + temp.len;
            }
            }
        }
        for(int i = 2; i <= n; ++i)
        {
        System.out.println(dist[i]);
        }
    }
}