题目描述

朴素版

package tulun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 奶牛回家1 {

    /**
     * 存在自环
     * 无向图，双向连通
     * @param args
     */
    static int N=60,inf=(int) 1e9,p,mi=inf,u=0;
    static int d[][]=new int [N][N];
    static int dist[]=new int [N];
    static boolean st[]=new boolean [N];

    public static int  change(String p) {
        char m=p.charAt(0);
        if(m>='A' && m<='Z'){
            return m-64;
        }
        else {
            return m-96+26;
        }
    }

    public static void dijkstra () {

        dist[26]=0;

        for(int i=1;i<=52;i++){

            int t=-1;
            for(int j=1;j<=52;j++){
                if(!st[j] && ( t==-1 || dist[t] >dist[j])){
                    t=j;
                }
            }

            for(int j=1;j<=52;j++){
                dist[j] = Math.min(dist[j], d[t][j]+dist[t]);
                if(dist[j] < mi && j>=1 && j<=25){
                    mi=dist[j];
                    u=j;
                }
            }
            st[t]=true;

        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
    BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
    p=Integer.parseInt(bufferedReader.readLine());
    int a=0,b=0,w=0;
    Arrays.fill(dist, inf);
   for(int i=1;i<N;i++){
       Arrays.fill(d[i], inf);
   }

    for(int i=1;i<=p;i++){
        String pString[]=bufferedReader.readLine().split(" ");

        a=change(pString[0]);
        b=change(pString[1]);
        w=Integer.parseInt(pString[2]);

        d[a][b]=Math.min(w, d[a][b]);
        d[b][a]=Math.min(w, d[b][a]);
    }

    dijkstra();
    char ans=(char) (u+64);
    System.out.println(ans+" "+mi);
    }

}

package tulun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

class Pairs  {
    int point;
    int distance;
    public Pairs(int point, int distance) {
        super();
        this.point = point;
        this.distance = distance;
    }

}

public class 奶牛回家 {

    /**
     * @param args
     */
    static int P=10010,M=60,idx=0;
    static int e[]=new int [P];
    static int h[]=new int [M];
    static int ne[]=new int [P];
    static int w[]=new int [P];
    static int inf =(int) 1e9,p;
    static int dist[]=new int [P];
    static boolean st[]=new boolean[P];
    static int mi=Integer.MAX_VALUE,u=0;
    public static void  init() {
        Arrays.fill(h, -1);
    }
    public static void  add(int a,int b,int c) {
        e[idx]=b;
        ne[idx]=h[a];
        w[idx]=c;
        h[a]=idx++;

    }

    public static void  dijkstra() {
        Queue<Pairs> queue = new PriorityQueue<Pairs>(1,new Comparator<Pairs>() {

            @Override
            public int compare(Pairs s, Pairs ss) {
                // TODO Auto-generated method stub
                return s.distance>ss.distance?1:-1;
            }

        });

        queue.offer(new Pairs(26, 0));
        dist[26]=0;
        while(!queue.isEmpty()){
            Pairs pairs1=queue.poll();
            int po=pairs1.point;
            int di=pairs1.distance;
            if(st[po]) continue;
            else {
                st[po]=true;
            }

            for(int i=h[po];i!=-1;i=ne[i]){
                int j=e[i];

                if(dist[j] > di+w[i]){

                    dist[j]=di+w[i];
                    if(j>=1 && j<=25 && mi>dist[j]){
                        mi=dist[j];
                        u=j;
                    }
                    queue.offer(new Pairs(j, dist[j]));
                }
            }
        }

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
    BufferedReader bufferedReader =new BufferedReader(new InputStreamReader(System.in));
    p=Integer.parseInt(bufferedReader.readLine());
    Arrays.fill(dist, inf);

    int a=0,b=0,w=0;
    init();
    for(int i=1;i<=p;i++){
        String p1[]=bufferedReader.readLine().split(" ");
        char s[]=p1[0].toCharArray();

        a=s[0]-64;
        s=p1[1].toCharArray();
        b=s[0]-64;
        w=Integer.parseInt(p1[2]);

        add(a, b, w);
        add(b, a, w);
    }
    dijkstra();
    char x=(char) (u+64);

    System.out.println(x+" "+mi);

}
}