C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N = 1e4 + 10;
//用200是因为A~Z:65~90,a~z:97~122
int h[200],e[2 * N],ne[2 * N],w[2 * N],idx;//无向图M = 2 * N
int d[200];
int cnt;
int z = 90;//牛棚
int p;
bool st[N];
priority_queue<PII,vector<PII>,greater<PII>> heap;
struct Cow{
char c;//存字母或者说编号
bool operator < (const Cow &cow) const{//用于sort
return d[c] < d[cow.c];
}
}cows[N];//存所有奶牛
void add(int a,int b,int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx++;
}
void heap_dijkstra(){
memset(d,0x3f,sizeof d);
d[z] = 0;
heap.push({0,z});
while(heap.size()){
PII t = heap.top();
int t1 = t.first,t2 = t.second;
heap.pop();
if(!st[t2]){
st[t2] = true;
for(int i = h[t2];i != -1;i = ne[i]){
int j = e[i];
if(d[j] > t1 + w[i]){
d[j] = t1 + w[i];
heap.push({d[j],j});
}
}
}
}
}
int main(){
memset(h,-1,sizeof h);
scanf("%d",&p);
char a[2],b[2];
int c;
while(p--){
scanf("%s%s%d",a,b,&c);
//有奶牛的存一下字母
if(*a >= 'A' && *a < 'Z') cows[cnt++] = {*a};
if(*b >= 'A' && *b < 'Z') cows[cnt++] = {*b};
//无向图存两次
add(*a,*b,c);
add(*b,*a,c);
}
dijkstra();
//将所有奶牛到Z距离排序
sort(cows,cows + cnt);
cout << cows[0].c << " " << d[cows[0].c] <<endl;
return 0;
}