USACO Section 2.4 Bessie Come Home - 无限水法..Floyd模板题..囧..

Floyd模板水题..要注意的是因为给的边数显然是可能大于所有可能边数的..也就是两点间可能有多条路..在读入是判断下..再一个很重要!!..是无向边!!我就因为搞成有向边给WA了一次..

Program:

/*  
ID: zzyzzy12  
LANG: C++  
TASK: comehome
*/    
#include<iostream>    
#include<istream>
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<stack>
#include<algorithm>    
#include<queue> 
using namespace std;   
int d[101][101],p,i,j,k;
char c;
int getdata()
{
     c='1';
     while (!(c>='A' && c<='Z') && !(c>='a' && c<='z')) c=getchar();  
     if (c>='A' && c<='Z') return c-'A'+1+26;
     return c-'a'+1; 
}
void Floyd()
{
     int i,j,k;
     for (k=1;k<=52;k++)
        for (i=1;i<=52;i++)
           for (j=1;j<=52;j++)
              if (d[i][j]-d[i][k]>d[k][j])
                 d[i][j]=d[i][k]+d[k][j];     
}
int main()
{
     freopen("comehome.in","r",stdin);  
     freopen("comehome.out","w",stdout);   
     memset(d,0x7f,sizeof(d));
     scanf("%d",&p);
     while (p--)
     {
            i=getdata();
            j=getdata();
            scanf("%d",&k);
            if (d[i][j]>k) d[i][j]=d[j][i]=k;   
     }
     Floyd();
     int ans=27;
     for (i=27;i<52;i++)
       if (d[i][52]<d[ans][52])
         ans=i;
     printf("%c %d\n",'A'+ans-26-1,d[ans][52]);
     return 0;   
}