AcWing 1375. 奶牛回家
原题链接
简单
作者:
吴鑫
,
2021-01-29 12:37:05
,
所有人可见
,
阅读 496
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=60;
int g[N][N];
int d[N];
bool st[N];
int m;
int get(char a){
if(a<='Z') return a-'A'+1;
return a-'a'+27;
}
int dijkstra(){
memset(d,0x3f,sizeof d);
d[26]=0;
for(int i=0;i<52;i++){
int t=-1;
for(int j=1;j<=52;j++)
if(!st[j]&&(t==-1||d[t]>d[j]))
t=j;
st[t]=true;
for(int j=1;j<=52;j++)
d[j]=min(d[j],d[t]+g[t][j]);
}
int k=1;
for(int i=2;i<26;i++)
if(d[k]>d[i]) k=i;
return k;
}
int main(){
cin>>m;
memset(g,0x3f,sizeof g);
for(;m;m--){
char a,b;
int c;
cin>>a>>b>>c;
int x=get(a),y=get(b);
g[x][y]=g[y][x]=min(g[x][y],c);
}
int k=dijkstra();
cout<<char('A'+k-1)<<" "<<d[k];
return 0;
}