题目分析

题中要求A~Y最先到达Z的牧场奶牛，
可能一开始的思路是遍历A~Z的牧场，计算到达Z的最小路径，再找出其中的最小值。
但可以换个思路，该题起点不同，但终点相同，
可以选择从终点Z出发，使用一次Dijkstra算法，就可以得到到剩余各个顶点的最短距离（存储在dist数组内）
其中dist值最小的牧场，就是所求的答案。

/*题中要求A~Y最先到达Z的牧场奶牛，
可能一开始的思路是遍历A~Z的牧场，计算到达Z的最小路径，再找出其中的最小值。
但可以换个思路，该题起点不同，但终点相同，
可以选择从终点Z出发，使用一次Dijkstra算法，就可以得到到剩余各个顶点的最短距离（存储在dist数组内）
其中dist值最小的牧场，就是所求的答案*/
#include <iostream>
#include <cstring>
using namespace std;
const int N=60,M=20010;
//1~26对应A~Z，33~58对应a~z（利用asc编码）
int g[N][N];
bool st[N];
int dist[N];

void dijkstra(int x){
    memset(dist,0x3f,sizeof dist);
    dist[x]=0;
    for(int i=0;i<58-1;i++){
        int t=-1;
        for(int j=1;j<=58;j++){
            if(!st[j]&&(t==-1||dist[j]<dist[t])) t=j;
        }
        st[t]=true;
        for(int j=1;j<=58;j++){
            if(!st[j]){
                dist[j]=min(dist[j],dist[t]+g[t][j]);
            }
        }
    }
}

int main(){
    int P;
    cin>>P;
    memset(g,0x3f,sizeof g);
    while(P--){
        char a,b;
        int c;
        cin>>a>>b>>c;
        int x=a-'A'+1,y=b-'A'+1,z=c;  //将char转化为int
        g[x][y]=g[y][x]=min(g[x][y],z);  //重边，自环
    }
    dijkstra('Z'-'A'+1);  //计算从Z出发，到各个顶点的距离
    int cow;
    int path=0x3f3f3f3f;
    for(int i=1;i<26;i++){
        if(dist[i]<path){  //遍历，寻找最小dist
            cow=i;
            path=dist[i];
        }
    }
    char rescow=cow+'A'-1;
    cout<<rescow<<" "<<path;
    return 0;
}