USACO2.4.4单源最短路FLOYD快速实现

其实用dijstra应该更快，可以把“Z”点看做起点，依次到其他点的距离求出即可，然后求最小，因为顶点时在50个左右，

FLOYD又可以将其秒杀……不过要注意的是，大小写字母代表不同的地方……

#include<stdio.h>

#define MAX 0x3fffffff
int dist[60][60];
bool hash[30];

int zhuan(char temp)
{
    int ge;
    if(temp>='a'&&temp<='z')
        return temp-'a'+1+26;
    if(temp>='A'&&temp<='Z')
    {
        ge=temp-'A'+1;
        hash[ge]=1;
        return temp-'A'+1;
    }
}

int main()
{
    int n,i,j,k,temp,f,s,min,minf;
    char a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=52;i++)
        {
            for(j=1;j<=52;j++)
            {
                dist[i][j]=MAX;
            }
            hash[i]=0;
        }

        for(i=1;i<=n;i++)
        {
            getchar();
            scanf("%c %c",&a,&b);
            scanf("%d",&temp);
            f=zhuan(a);
            s=zhuan(b);
            if(temp<dist[f][s])
            {
            dist[f][s]=temp;
            dist[s][f]=temp;
            }
        }

        for(k=1;k<=52;k++)
        {
            for(i=1;i<=52;i++)
            {
                for(j=1;j<=52;j++)
                {
                    if(dist[i][j]>dist[i][k]+dist[k][j])
                        dist[i][j]=dist[i][k]+dist[k][j];
                }
            }
        }
        min=MAX;
        for(i=1;i<=25;i++)
        {
            if(hash[i]==1)
            {
                if(min>dist[i][26])
                {
                    min=dist[i][26];
                    minf=i;
                }
            }
        }
        
        printf("%c %d\n",minf+'A'-1,min);
    }
}