AcWing 1375. 奶牛回家
原题链接
简单
作者:
Abide_HAO
,
2023-10-31 20:41:32
,
所有人可见
,
阅读 50
奶牛回家
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=60;
int dist[N];
int g[N][N];
bool st[N];
int n,m,ans=1;
int get(char x){//把字母转换成数字
if(x>='A'&&x<='Z')return x-'A'+1;
if(x>='a'&&x<='z')return x-'a'+1+26;
}
void dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[26]=0;////从终点'Z'开始走
for(int i=0;i<52;i++){//最多遍历52次,因为有52个英文字母
int t=-1;
for(int j=1;j<=52;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))t=j;
st[t]=true;
for(int j=1;j<=52;j++)
dist[j]=min(dist[j],dist[t]+g[t][j]);
}
for(int i=2;i<=25;i++)//更新ans
if(dist[i]<dist[ans])
ans=i;
}
int main(){
cin>>m;
memset(g,0x3f,sizeof g);
while(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);
}
dijkstra();
cout<<char(ans-1+'A')<<" "<<dist[ans]<<endl;
return 0;
}