三十一 1375. 奶牛回家 (最短路)

1375. 奶牛回家 (最短路)

略

import java.util.*;

public class Main {
    private static final int N = 60, INF = 0x3f3f3f3f;
    private static int n = 52, m;
    private static int[][] g = new int[N][N];
    private static int[] dist = new int[N];
    private static boolean[] st = new boolean[N];
    
    private static int charToInt(char a) {
        if (a <= 'Z') {
            return a - 'A' + 1;
        }
        return a - 'a' + 27;
    }
    
    private static void dijkstra() {
        Arrays.fill(dist, INF);
        dist[26] = 0;
        for (int i = 0; i < n - 1; i++) {
            int t = -1;
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[j] < dist[t])) {
                    t = j;
                }
            }
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        m = sc.nextInt();
        for (int i = 0; i < N; i++) {
            Arrays.fill(g[i], INF);
        }
        sc.nextLine();
        
        while (m-- > 0) {
            String str = sc.nextLine();
            char a = str.charAt(0);
            char b = str.charAt(2);
            int c = Integer.parseInt(String.valueOf(str.charAt(4)));
            int x = charToInt(a), y = charToInt(b);
            g[x][y] = g[y][x] = Math.min(g[x][y], c);
        }
        
        dijkstra();
        
        int res = 1;
        for (int i = 2; i <= 25; i++) {
            if (dist[i] < dist[res]) {
                res = i;
            }
        }
        
        System.out.println((char)(res - 1 + 'A') + " " + dist[res]);
    }
}