Java P1546 [USACO3.1]最短网络 Agri-Net

题目链接
裸的prim板子

import java.util.*;
public class Main {
    static int N = 110, INF = 1 << 29;

    static int g[][] = new int[N][N];
    static boolean st[] = new boolean[N];
    static int dist[] = new int[N];
    static int n;

    static int prim() {
        int res = 0;

        Arrays.fill(dist, INF);
        //System.out.println(1);
        dist[1] = 0;
        for(int i = 0; i < n; i ++ ) {
            //System.out.println(2);
            int t = -1;
            for(int j = 1; j <= n; j ++ )
                if(!st[j] && (t == -1 || dist[j] < dist[t]))
                    t = j;

            st[t] = true;
            res += dist[t];

            for(int j = 1; j <= n; j ++ )
                dist[j] = Math.min(dist[j], g[j][t]);

            //System.out.println(st);
        }

        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        for(int i = 1; i <= n; i ++ )
            for(int j = 1; j <= n; j ++ )
                g[i][j] = sc.nextInt();
        //System.out.println(1);

        System.out.println(prim());
    }
}