星星灰暗着。

星星灰暗着。

你所见的的确是一个NOIp退役OIer的博客。

题解 P1529 【回家 Bessie Come Home】

posted on 2017-05-16 14:57:17 | under 题解 |

真不是很懂你们用SPFA或者DJ的

明明是一个Floyd_只要不作死弄成单向图_可以搞定的事情

注意判定一下有无奶牛的事就可以了

#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;
}