题解 P1529 【回家 Bessie Come Home】
ShineEternal
2019-07-03 10:30:15
### 吐槽区：
~~我就想知道能不能仔细看看数据范围啊~~
----
进入正题：
本题显然就是个裸的最短路模板题，适用于**所有**算法。
和其他此类题目不同的是，本题没有直接在输入中给出牧场数的范围，但仔细想想字母，
**大小写加起来一共才56个**
这就意味着可以Floyd
我们可以把读入的字母都转换成1~56，甚至懒一些（比如我），直接把字母的ASCII码搬过来也能$O(n^3)$
> code:
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int f[505][505];
int main()
{
int m;
scanf("%d",&m);
char c1,c2;
int z;
for(int i=1;i<=500;i++)
{
for(int j=1;j<=500;j++)
{
f[i][j]=1000000000;
}
}
int maxn=0;
for(int i=1;i<=m;i++)
{
cin>>c1>>c2>>z;
int tmp1=c1,tmp2=c2;
f[tmp2][tmp1]=f[tmp1][tmp2]=min(f[tmp1][tmp2],z);
maxn=max(maxn,max(tmp1,tmp2));
}
for(int k=1;k<=maxn;k++)
{
for(int i=1;i<=maxn;i++)
{
for(int j=1;j<=maxn;j++)
{
//if(j!=i&&j!=k&&i!=j)
f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
}
}
char tag;
int ans=2147483647;
for(char i='A';i<='Y';i++)
{
int j=i;
if(f[j][90]<ans)
{
ans=f[j][90];
tag=i;
}
}
printf("%c %d\n",tag,ans);
return 0;
}
```
撒花~