最多52(a-z,A-Z)个点,所用有请floyd!!!
代码看一遍就很好理解做法啦文章来源:https://www.toymoban.com/news/detail-553742.html
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
string s1,s2;
int dist[60][60],d,p,ans=inf;
char ansc;
int getnum(char c){
if(c>='a'&&c<='z')return c-'a'+26;
else return c-'A';
}
void floyd(){
for(int k=0;k<60;k++)
for(int i=0;i<60;i++)
for(int j=0;j<60;j++)
dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
void init(){
for(int i=0;i<60;i++)
for(int j=0;j<60;j++)
dist[i][j]=inf-1;
}
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
init();
cin>>p;
while(p--){
cin>>s1>>s2>>d;
int x= getnum(s1[0]);
int y=getnum(s2[0]);
dist[x][y]=min(dist[x][y],d);
dist[y][x]=min(dist[y][x],d);
}
floyd();
for(int i=0;i<25;i++){
if(dist[i][25]<=ans){
ans=dist[i][25];ansc=i+'A';
}
}
cout<<ansc<<" "<<ans<<"\n";
return 0;
}
over~文章来源地址https://www.toymoban.com/news/detail-553742.html
到了这里,关于[洛谷]P1529 [USACO2.4] 回家 Bessie Come Home的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!