题解 P1529 【回家 Bessie Come Home】

##**真不是很懂你们用SPFA或者DJ的** 明明是一个Floyd\_只要不作死弄成单向图\_可以搞定的事情 注意判定一下有无奶牛的事就可以了 ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define ff(i,a,b) for(i=a;i<=b;i++)//预定义 using namespace std; int n,minn=100000000,minm; int f[60][60]; bool s[60]; char instead[10]; int main() { int i,j,k,z,xx,yy; char x,y; scanf("%d",&n);gets(instead); ff(i,1,52) ff(j,1,52) { if(i!=j)f[i][j]=100000000; } ff(i,1,n) { scanf("%c %c %d",&x,&y,&z); if(x>='A'&&x<='Z')s[x-'A'+1]=1,xx=x-'A'+1; else xx=x-'a'+27; if(y>='A'&&y<='Z')s[y-'A'+1]=1,yy=y-'A'+1; else yy=y-'a'+27; if(z<f[xx][yy])f[xx][yy]=f[yy][xx]=z; gets(instead);//由于洛谷那令人蛋疼的输入格式，特此用字符串解决问题 } s[26]=0;//'Z'无奶牛 //ff(i,1,52)printf("%d ",s[i]); ff(k,1,52) ff(i,1,52) ff(j,1,52) { f[i][j]=min(f[i][j],f[i][k]+f[k][j]); } ff(i,1,51)if(f[i][26]<minn&&s[i]==1)minn=f[i][26],minm=i; printf("%c %d\n",minm+'A'-1,minn); return 0; } ```